Komplexität der Erkennung von vertextransitiven Graphen

16

Ich kenne mich auf dem Gebiet der Komplexitätstheorie mit Gruppen nicht aus und entschuldige mich, wenn dies ein bekanntes Ergebnis ist.

Frage 1. Sei ein einfacher ungerichteter Graph der Ordnung n . Was ist die rechnerische Komplexität (in Bezug auf n ) der Bestimmung, ob G vertextransitiv ist?GnnG

Recall , dass ein Graph ist ecken transitive wenn A u t ( G ) wirkt transitiv aufGAut(G)V(G).

Ich bin nicht sicher, ob die obige Definition einen polynomialen Zeitalgorithmus zulässt, da es sein kann, dass die Reihenfolge von exponentiell ist.Aut(G)

Vertex-transitive Graphen weisen jedoch einige andere strukturelle Eigenschaften auf, die möglicherweise ausgenutzt werden, um sie effizient bestimmen zu können, sodass ich nicht sicher bin, wie der Status der obigen Frage ist.

Eine weitere interessante Unterklasse von vertextransitiven Graphen mit noch größerer Struktur ist die Klasse der Cayley- Graphen. Daher ist es selbstverständlich, auch die folgende verwandte Frage zu stellen

Frage 2. Wie komplex ist die Berechnung, um festzustellen, ob ein Graph ein Cayley-Graph ist?G

Jernej
quelle
3
Obwohl die Automorphismusgruppe überexponentiell sein kann, kann sie meines Erachtens im Polynomraum dargestellt werden, da die minimale Anzahl von Generatoren höchstens logarithmisch in |Aut(G)|
Timothy Sun
2
Es ist zu beachten, dass jeder vertextransitive Graph ein Cayley-Schrier-Graph ist: Es gibt eine Gruppe mit der Erzeugungsmenge S und der Untergruppe H, so dass die Vertices des Graphen die Nebenmengen G / H sind und zwei Nebenmengen durch eine Kante verbunden sind, wenn es welche gibt Element von S nimmt eins zum anderen. GSHG/HS
Joshua Grochow
Siehe auch
Peter Heinig

Antworten:

14

Ich habe keine vollständige Antwort, aber ich denke, beide Probleme sind offen.


Die Arbeit von Jajcay, Malnič, Marušič [3] bezieht sich auf Ihre erste Frage. Sie bieten einige Tools zum Testen der Vertex-Transitivität. In der Einleitung heißt es:

Für einen gegebenen endlichen Graphen ist es ausgesprochen schwierig zu bestimmen, ob Γ vertextransitiv ist, und die endgültige Antwort kommt normalerweise erst, nachdem ein wesentlicher Teil der vollständigen Automorphismusgruppe von Γ bestimmt wurde.ΓΓΓ

Es ist zu beachten, dass der Vertex-Transitivitäts-Test durchgeführt werden kann, indem der Isomorphismus des Graphen Mal getestet wird . Zwei Kopien G und G ' des Diagramms, mit speziellen Ankern (wie Wegen der Länge n + 1 ) bei u V ( G ) und v V ( G ' ) . Es gibt nur dann einen Isomorphismus zwischen G und G ', wenn der ursprüngliche Graph einen Automorphismus aufweist, der u auf v abbildet . Auf diese Weise können Sie die Vertex-Transitivität testen, indem Sie einen Vertex korrigierenn1GGn+1uV(G)vV(G)GGuv und prüfen, ob es Automorphismen gibt, die x auf alle anderen Scheitelpunkteabbilden.xx

Beachten Sie auch, dass wenn der Vertex-Transitivitäts-Test in Polynom-Zeit durchgeführt werden kann, dies auch der Isomorphismus-Test für vertex-transitive Graphen ist. Dies liegt daran, dass zwei vertextransitive Graphen genau dann isomorph sind, wenn ihre disjunkte Vereinigung vertextransitiv ist. Ich glaube, dass die Komplexität des Graphisomorphismus für vertextransitive Graphen nicht bekannt ist.


Für die 2. Frage habe ich ein Teilergebnis gefunden. Ein Kreislaufdiagramm ist ein Cayley-Diagramm für eine zyklische Gruppe. Evdokimov und Ponomarenko [2] zeigen, dass die Erkennung von Kreislaufkurven in polynomialer Zeit erfolgen kann. Auch das Buchkapitel von Alspach [1, Kapitel 6: Cayley-Graphen, Abschnitt 6.2: Erkennung] wäre für Sie interessant, obwohl es besagt, dass:

Wir werden das Rechenproblem der Erkennung, ob ein beliebiger Graph ein Cayley-Graph ist, ignorieren. Stattdessen nehmen wir immer an, dass Cayley-Graphen in Bezug auf die Gruppen, auf denen sie aufgebaut sind, zusammen mit den Verbindungssätzen beschrieben wurden. Für die meisten Probleme ist dies kein Nachteil.


  1. Beineke, Wilson, Cameron. Themen in der algebraischen Graphentheorie . Cambridge University Press, 2004.
  2. Evdokimov, Ponomarenko. Zirkulante Graphen: Erkennung und Isomorphismustest in Polynomzeit. St. Petersburg Math. J. 15 (2004) 813 & ndash; 835. doi: 10.1090 / S1061-0022-04-00833-7
  3. Jajcay, Malnič, Marušič. Über die Anzahl der geschlossenen Gänge in vertextransitiven Graphen. Diskrete Mathematik. 307 (2007) 484-493. doi: 10.1016 / j.disc.2005.09.039
Yota Otachi
quelle
4
Tatsächlich kann die Vertex-Transitivität mithilfe von Graphisomorphismustests getestet werden: Fixiere einen Vertex x und überprüfe, ob es einen Automorphismus gibt, der x an einen beliebigen anderen Vertex sendet . n1xx
Yuval Filmus