The Parallel Complexity of Graph Canonization Under Abelian Group Action

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.

1. 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 $mathbb {F} _{2}$ . This implies a deterministic NC ² algorithm for the problem.
2. 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 ³ and randomized NC ² algorithms for the problem.