Graphisomorphismus und die Automorphismusgruppe

Ein üblicher Ansatz, um zu entscheiden, ob zwei gegebene Graphen isomorph sind, besteht darin, die sogenannte kanonische Bezeichnung (alternativ kanonischer Graph) jedes Graphen zu berechnen und zu überprüfen, ob diese übereinstimmen oder nicht.

Tools wie Nauty berechnen den kanonischen Graphen über Suchbäume, die mit einigen cleveren Ideen beschnitten werden, die sich unter anderem auf Graph-Automorphismen stützen. Aus diesem Grund ermöglicht Nauty die Berechnung eines Generators der Graph Automorphism Group. Soweit ich die Idee hinter Nauty verstanden habe, erfordert die Berechnung des kanonischen Graphen jedoch nicht die Berechnung eines Generators der Graph-Automorphismus-Gruppe im Allgemeinen.

Meine Frage lautet daher: Gibt es eine formale komplexitätstheoretische Beziehung zwischen GI und der Berechnung eines Generatorsatzes der Graph-Automorphismus-Gruppe?

Danke vielmals.

complexity-theory graph-isomorphism user88338
quelle

Wir können über die Automorphismusgruppe von

bestimmen, ob

G

$G$ und

H

$H$ isomorph sind . Wenn ich in die andere Richtung gehe, bin ich mir nicht sicher - vielleicht gibt es eine einfache Möglichkeit, ein Diagramm aufgrund seiner Automorphismusgruppe kanonisch zu kennzeichnen.

G \cup H

$G \cup H$

Rebecca J. Stones

@ RebeccaJ.Stones, ist das aber die gleiche Frage? Sofern Wikipedia nicht veraltet ist, ist nicht bekannt, ob Graphisomorphismus und Graphkanonisierung polynomialzeitäquivalent sind. Ich glaube daher nicht, dass ein Algorithmus zum kanonischen Beschriften eines Graphen aus der Automorphismusgruppe etwas Nützliches über die Beziehung zwischen Computing aussagen würde die Gruppe und GI.

Peter Taylor

Antworten:

Wie aus den Kommentaren hervorgeht, kann es zu Verwirrung darüber kommen, was Sie "GI" nennen. Aber die Idee hier ist richtig. Es ist Polynom-Zeit-Äquivalent, Generatoren einer Automorphismusgruppe zu finden, wie es ist, einen Isomorphismus zwischen zwei Gruppen zu finden. Die Idee ist insofern "klassisch", als sie in frühen Arbeiten wie Luks 'Gruppenisomorphismus in begrenzter Valenz in der Polynomzeit vorkommt, und selbst dort denke ich, dass die Idee als "bekannt" angesehen wurde.

Anspruch. Lassen Sie und sein verbundenen Graphen. Dann , wenn, und nur wenn, jeder Generatorsatz von enthält ein Element , so dass . $G$ $H$ $G\cong H$ $S$ $\mathrm{Aut}(G\sqcup H)$ $g\in S$ $G^g=H$

$\mathrm{Aut}(G\times H)$ $G$ $H$ $G\cong H$

$\mathrm{Aut}(G\sqcup H)$ $G$ $H$ $G\cong H$ $G$

$\mathrm{Aut}(G\sqcup H)$ $S$ $G$ $G$ $H$ $H$ $G$ $H$ $G$ $H$ $H$ $G$ $|G|=|H|$ $S$ $G$ $G$ $S$ $G$ $G$ $S$ $G$ $G$ $H$ $H$ $\mathrm{Aut}(G\sqcup H)$ $G$ $H$

$G\cong H$ $\phi:G\to H$ $\phi\sqcup \phi^{-1}$ $G\sqcup H$ $\mathrm{Aut}(G\sqcup H)$ $G$ $H$ $G\not\cong H$ $\Box$

Aber jetzt muss klar sein, dass von der Entscheidung (Ist ?) Zur Suche (Gib mir oder ein Zertifikat, dass ) noch zu streiten ist ( und kann sein). Auch von einem Isomorphismus zu Generatoren von Automorphismen ist ein weiteres Argument (individualisieren Sie die Graphen und wiederholen Sie den Isomorphismustest). Alles in allem haben Sie also ein paar Seiten mit Argumenten, um diese Äquivalenzen herzustellen. Keiner zeigt jedoch eine kanonische Kennzeichnung. Das ist viel schwieriger (NP-schwer, wenn ich mich recht erinnere). Obwohl NAutY und Traces viele Beispiele schnell verarbeiten. $G\cong H$ $\phi:G\to H$ $G\not\cong H$

Algeboy
quelle