On the complexity of isomorphism testing for restricted classes of graphs
Dissertation
Faculties
Fakultät für Ingenieurwissenschaften und InformatikAbstract
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.
Date created
2010
Subject headings
[GND]: Graphenisomorphie[LCSH]: Computational complexity | Graph theory
[Free subject headings]: Graph isomorphism | Reachability
[DDC subject group]: DDC 004 / Data processing & computer science
Metadata
Show full item recordDOI & citation
Please use this identifier to cite or link to this item: http://dx.doi.org/10.18725/OPARU-3896
Wagner, Fabian (2010): On the complexity of isomorphism testing for restricted classes of graphs. Open Access Repositorium der Universität Ulm und Technischen Hochschule Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-3896
Citation formatter >