Completeness results for graph isomorphism

✍ Scribed by Birgit Jenner; Johannes Köbler; Pierre McKenzie; Jacobo Torán

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 239 KB
• Volume: 66
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(03)00042-4

✦ Synopsis

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 NC 2 . In particular we show that tree isomorphism, when trees are encoded as strings, is NC 1 -hard under AC 0 -reductions. NC 1completeness thus follows from Buss's NC 1 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.