„Winziger“ Graph-Isomorphismus

19

Während ich über die Komplexität des Testens der Isomorphie asymmetrischer Graphen nachdachte (siehe meine verwandte Frage zur Theorie), kam mir eine ergänzende Frage in den Sinn.

Angenommen, wir haben eine Polynomzeit-Turing-Maschine , die am Eingang 1 n einen Graphen G M , n mit n Knoten erzeugt.M1nGM,nn

Wir können das Problem :ΠM

("Winziger" GI): Gegeben ein Graph , ist G isomorph zu G M , | V | ?G=(V,E)GGM,|V|

Mit anderen Worten, wir müssen ein gegebenes Diagramm mit einem "Referenz" -Diagramm gleicher Größe vergleichen, das von einer Turingmaschine fester Polynomzeit erzeugt wird .M

Für alle Polynomzeit Turingmaschinen , haben wir Π MN P , und für viele von ihnen haben wir Π MP . Aber ist es wahr für alle M ? Ist das Problem bekannt?MΠMNPΠMP
M

Auf den ersten Blick dachte ich, dass jedes viel einfacher sein sollte als G I , weil es für jedes n nur einen "Referenz" -Graphen dieser Größe gibt und vielleicht die Symmetrien / Asymmetrien der von M erzeugten Graphen ausgenutzt werden können Es kann ein effizienter Ad-hoc-Isomorphismus-Tester gebaut werden ... aber es ist nicht wahr: M kann eine Art polynomisch getaktete Universal-Turing-Maschine enthalten, die die (unäre) Eingabe 1 n verwendet , um völlig andere (in der Struktur) Referenzgraphen als n zu erzeugen steigt.ΠMGInMM1nn

Marzio De Biasi
quelle
Interessant, kennen Sie ein Beispiel für eine P-Zeit-Turing-Maschine , die einen Graphen G M , N erzeugt ? MGM,N
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Ein triviales Beispiel, für das , ein TM M ist , das einfach n isolierte Eckpunkte ausgibt (oder ein anderes ist ein TM, das K n ausgibt ). Ohne Verlust der Allgemeinheit können wir uns auch ein Modell vorstellen, bei dem jede Polynomzeit TM über dem binären Alphabet einen Referenzgraphen erzeugt: Wählen Sie einfach die ersten n 2 Bits des Bandes aus, nachdem es angehalten hat, und interpretieren Sie es als die Adjazenzmatrix von G M , n . ΠMPMnKnn2GM,n
Marzio De Biasi
Für TM die garantiert , dass G M , n Hamilton - Zyklus hat, dann denke ich Π M ist nicht in P . MGM,nΠMP
Mohammad Al-Turkistany
@ MohammadAl-Turkistany: Ich denke, es ist nicht wahr: Wähle einfach ein TM, das einfach einen Zyklus von Knoten aufbaut : Für alle n ist der Referenzgraph - der einen Hamilton-Zyklus hat - in der Polynomzeit leicht überprüfbar. Ich denke an ein nicht triviales Beispiel eines (ziemlich einfachen) Generators, für den es schwer zu zeigen scheint, dass das Problem in P liegt . aber ich möchte einige tests mit nauty machen, bevor ich sie der frage hinzufüge. nnP
Marzio De Biasi
1
Was ist mit dem GI "Itsy Bitsy", bei dem wir für ein festes M und N entscheiden müssen, ob die beiden auf 1 ^ n erzeugten Graphen gleich sind? (Dies ist eine unäre Sprache.)
Domotorp

Antworten:

6

[Dies sind eher ein paar erweiterte Kommentare als eine Antwort.]

1) Wenn , dann gibt es keine festpolynomielle Grenze für die Zeitkomplexität von allen Π M , auch für M , die nur Zeit brauchen , sagen wir n 3 : Wenn für alle Zeit n 3 M , Π MD T I M E ( n k ) , dann ist das Folgende ein Mehrfachzeitalgorithmus für GI. Konstruiere am Eingang ( G , H ) eine Turingmaschine M G mit einer Uhr, die dafür sorgt, dass M GGIPΠMMn3n3 MΠMDTIME(nk)(G,H)MGMGLäuft bei Eingaben der Größe n nie länger als Schritte , und zwar so, dass M G ( 1 | V ( G ) | ) = G ist , und löst dann Π M G ( H ) in der Zeit O ( n k ) .n3nMG(1|V(G)|)=GΠMG(H)O(nk)

2) Da für jeden , Π M nicht schwerer als GI ist, denke man könnte , dass das beste Ergebnis entlang der Linien von „ Π M in nicht zu sein scheint P “ konnte man hofft ein GI-Vollständigkeit Ergebnis. Es scheint mir jedoch unwahrscheinlich, dass ein Π M vollständig sein könnte, zumindest aus den folgenden Gründen:MΠMΠMPΠM

  • Alle mir bekannten GI-Vollständigkeitsergebnisse beziehen sich auf relativ große Klassen von Diagrammen, statt auf ein einzelnes Diagramm jeder Größe. Auch wenn Sie die Effizienzanforderung vollständig fallen lassen, sind mir keine Diagrammlisten so dass | V ( G n ) | = N (oder sogar p o l y ( n ) ) , so dass die Prüfung auf Isomorphismus G n GI-abgeschlossen ist.G1,G2,|V(Gn)|=npoly(n)Gn

  • In einem verwandten Punkt sind die meisten (alle?) GI-Vollständigkeitsergebnisse nicht nur Viel-Eins-Reduktionen, sondern haben die folgende Form: Es gibt eine Funktion so dass bei gegebener Instanz ( G , H ) von GI ( f ( G ) , f ( H ) ) ist eine Instanz des anderen GI-vollständigen Problems. (Dies sind nur polyzeitliche Morphismen von Äquivalenzrelationen oder das, was Fortnow und ich "Kernelreduktionen" nannten.) Wir können ohne weiteres bedingungslos zeigen, dass es keine solche Reduktion von GI auf Π M gibt (selbst wenn Sie die Definition so ändern, dass M zulässig istf(G,H)(f(G),f(H))ΠMMum mehrere Graphen auszugeben). Hinweis: Verschaffen Sie sich einen Widerspruch, indem Sie zeigen, dass das Bild eines solchen vollständig in { G M , n } n 0 enthalten sein muss .f{GM,n}n0

3) Auch wenn man basierend auf einem universellen TM konstruieren könnte, wie in der Frage vorgeschlagen, kann man vielleicht immer noch einen effizienten Tester konstruieren, nur nicht effizient. Das heißt, vielleicht für jeden M , Π M ist in P / p o l y ?MMΠMP/poly

Joshua Grochow
quelle
1

Ich habe keine Antwort auf Ihre Frage, schlage aber vor, eine eingeschränktere Version von in Betracht zu ziehen, für die wir zeigen können, dass sie in P liegt.ΠM

Betrachten wir nur Graphenfamilien, bei denen die Anzahl der Kanten logarithmisch zunimmt. Ich werde dies formalisieren, indem ich Ihre Problemformulierung umformuliere, auch um zu sehen, ob ich es richtig verstanden habe.

Ein ungerichteter Graph mit n Kanten kann durch ein n 2 - n beschrieben werdenGn lange Bitfolge, verketten Sie einfach die Einträge der Adjazenzmatrix vonGim oberen Dreieck. Daher gibt es2 n 2 - nn2n2G mögliche Graphen aufnEckpunkten. Daraus folgt, dass jede Funktionf:NN ist,so dass0f(n)<2n2-n ist2n2n2nf:NN für allenbeschreibt eine Familie von Graphen. Für jede effizient berechenbare solche Funktionfdefinieren wirΠfals GΠf0f(n)<2n2n2nfΠf

GΠfG is isomorph to the graph described by f(|V(G)|)

xb1(x)Πff

b1(f(n))O(logn)

Πf

fGnf(n)O(logn)O(logn)nO(logn)nweil wir alle Permutationen ausprobieren können. Wenn wir also einen Greedy-Algorithmus verwenden, um jedem MCC des Eingabegraphen einen MCC im Referenzgraphen zuzuweisen, können wir herausfinden, ob beide Graphen isomorph sind.

John D.
quelle
fnGΠfP
In der Tat scheint es ein leichteres Argument zu sein, als ich dachte. Ich werde es in meine Antwort aufnehmen.
John D.
Πf
1
O(logn/loglogn)(logn)!(logn)logn=nloglogn2vlogvO(logn/loglogn)O(log2n)