ECCC-Report TR10-050https://eccc.weizmann.ac.il/report/2010/050Comments and Revisions published for TR10-050en-usThu, 25 Mar 2010 13:09:57 +0200
Paper TR10-050
| Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space |
Samir Datta,
Prajakta Nimbhorkar,
Thomas Thierauf,
Fabian Wagner
https://eccc.weizmann.ac.il/report/2010/050Graph isomorphism is an important and widely studied computational problem, with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.
We extend this result of [DLN$^+$09] further
to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as
a minor, and give a log-space algorithm.
Our algorithm for $K_{3,3}$ minor-free graphs proceeds by decomposition into triconnected
components, which are known to be either planar or $K_5$ components [Vaz89]. This gives a triconnected
component tree similar to that for planar graphs. An extension of the log-space algorithm of [DLN$^+$09]
can then be used to decide the isomorphism problem.
For $K_5$ minor-free graphs, we consider $3$-connected components.
These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices
or, with a further decomposition, one obtains planar $4$-connected components [Khu88].
We give an algorithm to get a unique
decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components,
and construct trees, accordingly.
Since the algorithm of [DLN$^+$09] does
not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.Thu, 25 Mar 2010 13:09:57 +0200https://eccc.weizmann.ac.il/report/2010/050