Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Completeness Results for Graph Isomorphism

Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán


We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC2. In particular we show that tree isomorphism, when trees are encoded as strings, is NC1-hard under AC0-reductions. NC1-completeness thus follows from Buss's NC1 upper bound.

By contrast, we prove that testing isomorphism of two trees encoded as pointer lists is L-complete. Concerning colored graphs we show that the isomorphism problem for graphs with color multiplicities 2 and 3 is complete for symmetric logarithmic space SL under many-one reductions. This result improves the existing upper bounds for the problem. We also show that the graph automorphism problem for colored graphs with color classes of size 2 is equivalent to deciding whether a graph has more than a single connected component and we prove that for color classes of size 3 the graph automorphism problem is contained in SL.

Ps-File: Completeness Results for Graph Isomorphism