Space efficient algorithms for graph isomorphism and representation

Abstract

Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen.

The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).