Abstract
Birgit Jenner, Johannes Köbler, Pierre McKenzie, and Jacobo Torán
Abstract:
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.