The Parallel Complexity of Graph Canonization Under Abelian Group Action

The Parallel Complexity of Graph Canonization Under Abelian Group Action

0.00 Avg rating—0 Votes
Article ID: iaor20133654
Volume: 67
Issue: 2
Start Page Number: 247
End Page Number: 276
Publication Date: Oct 2013
Journal: Algorithmica
Authors: ,
Keywords: programming: linear
Abstract:

We study the problem of computing canonical forms for graphs and hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of computing canonical forms for graphs to the problem of computing canonical forms for associated algebraic structures, and we develop parallel algorithms for these associated problems.

  • In our first result we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is logspace Turing equivalent to solving a system of linear equations over the field 𝔽 2 . This implies a deterministic NC 2 algorithm for the problem.
  • Similarly, we show that the problem of canonical labeling graphs and hypergraphs under arbitrary Abelian permutation group action is fairly well characterized by the problem of computing the integer determinant. In particular, this yields deterministic NC 3 and randomized NC 2 algorithms for the problem.

    • Reviews

    Required fields are marked *. Your email address will not be published.