Die Frage, wie man wie schnell überprüfen kann, ob zwei Graphen eigentlich gleich sind, ist eine höchst knifflige. In Mathematik und Informatik wird das Problem des Graphenvergleichens als das "Graphen-Isomorphie-Problem" gehandelt - und ist dort ziemlich hoch angesiedelt.
Zweimal derselbe Graph? Oder doch zwei verschiedene Graphen?
Kein Wunder also, dass die Ankündigung eines Vortrags des Komplexitätstheoretikers László Babai von der Universität Chicago für kommenden Dienstag ziemlich hohe Welten in der Community schlägt: Babai behauptet, einen Algorithmus gefunden zu haben, der das Problem in "quasi-polynomieller" Zeit lösen kann. Quasi-polynomiell bedeutet, dass die Rechenzeit für Graphen mit n Knoten durch die Funktionen 2^O(log(n))^c beschränkt ist. Für c>1 bedeutet das: zwar langsamer als polynomiell, das mathematische Wort für "schnell", aber immer noch langsamer als exponentiell. Also sowas wie "ziemlich schnell".
Niemand weiß derzeit, ob es einen Algorithmus gibt, der das Graphenisomorphie-Problem wirklich schnell (also in polynomieller Zeit) lösen kann. Das Pikante: Es weiß auch niemand, ob das Problem NP-vollständig ist, sich also zu einem der Probleme vom Typ Travelling Salesman und SAT umformulieren lässt. Damit ist "GI" das letzte der 12 Probleme, die die Komplexitäts-Klassiker Michael Garey und David Johnson Ende der 1970er Jahre nicht einordnen konnten - für die anderen elf Problemfälle wurde inzwischen jeweils eine Zuordnung zu einer Komplexitätsklasse bewiesen. Für Problem 12 arbeitet sich Babai nun also mit seinem Algorithmus in Richtung Polyzeit vor.
Und er ist kein Neuling auf dem Gebiet: Der derzeit beste bekannte Algorithmus für "GI" stammt von ihm und Eugene Luks aus der Mitte der 1980er Jahre. Damals benutzte Babai Ergebnisse aus der Algebra (Gruppentheorie). Wie der nun gefundene Algorithmus aussieht, ist noch nicht bekannt - vermutlich basiert er auch auf Ergebnissen über Graphenstrukturen der letzten Jahre. In jedem Fall ist er wohl zu kompliziert, um demnächst in Computersoftware gegossen zu werden, die dann Graphen "ziemlich flott" vergleichen kann - auch wenn Netzwerk-Forscher sich das womöglich wünschen.
Nachtrag: Babai hat eine Arbeit veröffentlicht, in der er seinen Algorithmus beschreibt, und im Archiv hochgeladen: László Babai, Graph Isomorphism in Quasipolynomial Time, Preprint, 84 Seiten, Dezember 2015: http://arxiv.org/abs/1512.03547.
Andreas Loos