Canonizing Hypergraphs under Abelian Group Action

We study the problem of canonizing hypergraphs under Abelian group action and show tight complexity bounds. Our approach is algebraic. We transform the problem of graph canonization to the problem of canonizing associated algebraic structures for which we develop a parallel algorithm. Specifically, we show that the problem of computing canonical labelings for hypergraphs of color class size 2 is computable in FL⊕L. For general hypergraphs, under Abelian permutation group action, for the canonization problem we show an upper bound of randomized FLGapL (which is contained in randomized NC2). This is a nearly tight characterization since the problem is hard for the complexity class FLGapL. The problem is also in deterministic NC3.