Schnellster bekannter deterministischer Algorithmus für das ungerichtete Graph-Isomorphismus-Problem

Was ist der schnellste bekannte ungerichtete Graphisomorphismus-Algorithmus?

cc.complexity-theory reference-request graph-algorithms graph-isomorphism bbejot
quelle

Ich denke, es ist besser, wenn Sie nur nach dem schnellsten bekannten Algorithmus fragen und nicht nach der Richtigkeit des in der Veröffentlichung angegebenen Algorithmus (siehe insbesondere die entsprechende Meta-Frage ). Für mich ist das Abstract bereits eine rote Fahne (die Schlussfolgerungen scheinen auch falsche Informationen zu enthalten).

Juho

Wenn ein Hauptergebnis für ein berühmtes Problem korrekt ist, erscheint es im Allgemeinen in den berühmten Theorieblogs 1 2 und im Wikipedia-Artikel für das Problem .

Kaveh

Das Papier besteht den Geruchstest nicht. Es gibt vor, ein großes Problem zu lösen, erschien aber auf einer obskuren Konferenz. Es gibt keine Beweise. Die Korrektheit wird experimentell "validiert". Die Autoren denken, dass der Graphisomorphismus NP-hart ist.

Sasho Nikolov

@JoshuaGrochow sagt, dass der schnellste bekannte Algorithmus Zeit

braucht

in dieser Antwortcstheory.stackexchange.com/a/22059/4896. Ich denke, der Algorithmus ist deterministisch.

2^{\sqrt{n \log n}}

$2^{\sqrt{n\log n}}$

Sasho Nikolov

2^{O (\sqrt{n \log n})}

$2^{O(\sqrt {n \log n})}$

Antworten:

Die Forschung zum Graphisomorphismus ging im Allgemeinen dahin, effiziente oder verbesserte Algorithmen für viele spezielle Graphklassen mit P-Time-Algorithmen zu untersuchen, für die große Fortschritte erzielt wurden, sowie empirischere Analysen mit modernster Software, z Nauty betrachtet das durchschnittliche und das Worst-Case-Verhalten etwas getrennt. Für das allgemeine Problem ist laut dieser Blog-Umfrage von Bennett / Flammia / Harrow anscheinend ein altes Ergebnis von Babai / Luks das bekannteste.

"Kanonische Beschriftung des Graphen" von László Babai und Eugene M. Luks STOC 1983 ( Papier hier ) Dies beschreibt eine subexponentielle (oder, ähm, wie hat Scott dies genannt?) Exp (-n ^ {frac {1} { 2} + c}), Zeitalgorithmus für einen Graphen mit n Eckpunkten. Als Leseliste empfehle ich noch nicht, in dieses Papier einzusteigen, aber ich wollte nur Ihren Optimismus für einen klassischen Algorithmus zum Ausdruck bringen, indem ich Ihnen (a) zeige, dass das Beste, was wir im Allgemeinen haben, ein subexponentieller Zeitalgorithmus ist, (b) Dieser Rekord besteht seit fast drei Jahrzehnten, und (c) wenn man sich das Papier ansieht, sieht man, dass es nicht einfach ist. Hoffnung aufgeben alle, die eintreten?

Hier sind zwei weitere ziemlich umfassende Umfragen, um den Stand der Technik zu beurteilen, aber vielleicht mehr mit einer empirischen Ausrichtung.

Effiziente Algorithmen zum Testen des Graphisomorphismus Jose Luis Lopez Presa Doktorarbeit (2009)
Das Graph Isomorphism Problem (1996) Fortin (1996)

vzn
quelle

Ein weiterer Punkt ist, dass der Graph-Isomorphismus, wie in der Antwort von JGs, tiefe theoretische Verbindungen zum Problem des Gruppen-Isomorphismus aufweist. Dies kann in diesem anderen Blog auf Betreff von RJLipton gesehen werden, Ein Ansatz zur

Graphisomorphie

Beachten Sie, dass die Fortin-Umfrage fast 20 Jahre alt ist. Dies ist eine Ewigkeit in einem Bereich, in dem beispielsweise das Konzept der NP-Vollständigkeit nur etwa 40 Jahre alt ist.

David Richerby

Ja, das auch bemerkt, aber es gibt auch das Phänomen der TCS-Schlüssel- / Hard-Open-Probleme, die über Jahrzehnte nur geringe Fortschritte zeigen, offensichtlich auch P vs NP als kanonisches Beispiel dafür, und GI passt auch wie angegeben.

vzn

Sie scheinen die Aussagen "Wir haben das Problem noch nicht gelöst" und "Es wurden keine Fortschritte erzielt" zu verwirren.

David Richerby

$2^{\log n^{O(1)}}$

Mohammad Al-Turkistany
quelle

Angeblich läuft in quasipolynomialer Zeit. Selbst wenn seine Analyse fehlerhaft und lediglich subexponentiell ist, wird sie dennoch der schnellste Algorithmus sein.

Stella Biderman