Frontiers of Tractability for the Graph Isomorphism Problem

Recognizing isomorphism of two given graphs is one of the most
fundamental problems in theoretical computer science and applied
discrete mathematics. The problem is in the class NP, but its
complexity status is open since decades. If restricted to
a particular class of graphs, the problem can become solvable in polynomial time
or can stay as hard as in general. Our overall objective is to draw,
as sharp as possible, a borderline between these two cases.
This means that we have to inspect the borderland consisting of unclassified
classes of graphs. Furthermore, in a number of polynomial-time solvable
cases we intend to find more efficient, NC or Log-Space, algorithms.
Along with tackling important particular classes of graphs, we aim at
finding sufficient conditions allowing us, given a class of graphs,
to categorize it as isomorphism-tractable or isomorphism-complete.
Such conditions can be stated in terms of decomposability properties
with respect to modular and split decompositions, definability of graphs
in bounded logics, or growth types of hereditary classes of graphs.

The project has interconnections with finite model theory (the definability
issues), topological graph theory (isomorphism of maps on surfaces),
and computational geometry (equivalence relations between point configurations).

Principal Investigators
Verbitsky, Oleg Dr. (Details) (Algorithms and Complexity II)

Duration of Project
Start date: 08/2011
End date: 05/2015

Last updated on 2020-11-03 at 23:16