On the complexity of isomorphism testing for restricted classes of graphs

Abstract

The graph isomorphism problem GI consists of deciding whether there is a bijection between the vertices of two graphs, which preserves the adjacency relations. The problem is in NP but it is not known to be complete for this class [BHZ87,Sch88] nor in the class P. The best known lower bound is DET [Tor04]. This enormous gap has motivated a study of isomorphism restricted to special classes of graphs where this gap can be reduced. We prove for the classes of planar graphs, K_{3,3}-minor free and K_5-minor free graphs, that isomorphism testing is in logspace. For graphs of bounded treewidth we prove a new upper bound LogCFL. We also consider the complexity of the isomorphism problem on quasigroups, which are given in table representation. Besides isomorphism we also consider the reachability problem which asks in a directed graph with two designated vertices s and t, whether there is a path from s to t. We consider the complexity of the shortest path problem on planar graphs and reduce reachability on K_{3,3}-minor free and K_5-minor free directed graphs to reachability for planar directed graphs. This improves the existing upper bounds for the reachability problems on the mentioned graph classes.