Ist "Ist eine Permutation p ein Automorphismus eines Graphen in meiner Menge?" NP-complete?

13

Angenommen, wir haben eine Menge S von Graphen (endliche Graphen, aber eine unendliche Anzahl von Graphen) und eine Gruppe P von Permutationen, die auf S einwirken.

Instanz: Eine Permutation p in P.

Frage: Gibt es in S einen Graphen g, der den Automorphismus p zulässt?

Ist dieses Problem NP-vollständig für einige Sätze S?

Es wäre einfach zu überprüfen, ob ein Graph die Permutation p (dh das Zertifikat) zulässt. Darüber hinaus ist es einfach, Beispiele für S zu finden, bei denen das Problem nicht NP-vollständig ist, z. B. wenn S die Menge vollständiger Graphen ist, deren Antwort immer Ja lautet.

Hinweis: Es interessiert mich nicht wirklich, um welche Art von Grafiken es sich handelt. Wenn Sie möchten, können sie nicht einfach, gerichtet, gefärbt usw. sein.

ADDENDUM: Das Problem, mit dem ich mich derzeit befasse, besteht darin, zu klassifizieren, welche Isotopismen Autotopismen von lateinischen Quadraten sind (die auch als eine spezielle Art von Graphautomorphismus interpretiert werden können).

Ausgehend von einem lateinischen Quadrat L (i, j) können wir einen Graphen folgendermaßen konstruieren:

  • Die Scheitelmenge ist die Menge der Zellen (i, j) in der Matrix und
  • Es gibt eine Kante zwischen (i, j) und (i ', j'), wenn i = i 'oder j = j' oder L (i, j) = L (i ', j').

Ein solches Diagramm wird als lateinisches Quadrat-Diagramm bezeichnet (siehe z. B. diesen Artikel von Bailey und Cameron unter http://designtheory.org/library/encyc/topics/lsee.pdf ). Wir können einen Autotopismus eines lateinischen Quadrats als einen Automorphismus des lateinischen Quadratgraphen interpretieren. Sei S also die Menge lateinischer Quadratgraphen, die aus den lateinischen Quadraten der Ordnung n gebildet werden. Die Frage, die mich interessiert, ist:

Ist p bei gegebener Permutation p ein Automorphismus von einem (oder mehreren) der Graphen in S?

Ich habe das Gefühl, dass es im Allgemeinen schwierig ist, eine Frage zu beantworten - ich schreibe zurzeit eine mehr als 30-seitige Arbeit zu diesem Thema (mit 2 Mitautoren). Eigentlich ist es die meiste Zeit einfach (die meiste Zeit ist es "nein"), aber es gibt einige schwierige Fälle.

Daher bin ich daran interessiert, Entscheidungsprobleme zu finden, die mit der "Symmetrieklassifizierung" zusammenhängen. Sie müssen nicht unbedingt mit lateinischen Quadraten verwandt sein. Ich hoffe nur, dass ich diese Techniken verwenden kann, um die Frage nach lateinischen Quadraten zu beantworten.

Douglas S. Stones
quelle
Ich bin nicht sicher, ob ich das Problem richtig verstehe. Können Sie ein Beispiel für S und P (und die Gruppenaktion von P auf S) geben? Ein Beispiel, das das Problem nicht trivial macht (weder all-yes noch all-no), hilft, das Problem zu verstehen.
Tsuyoshi Ito
2
Im Beispiel vollständiger Graphen verstehe ich nicht, wie sich eine Permutation auf k Punkte auf den vollständigen Graphen auf n Punkte auswirkt, wobei k ≠ n ist (insbesondere wenn k> n ist).
Tsuyoshi Ito
Es gelang mir zu glauben, dass ich das Problem verstehe, aber jetzt habe ich entschieden, dass ich es nicht tue. Wirkt die Gruppe von Permutationen S auf die Graphen in der Familie P oder nur potentiell auf die Graphen in der Familie P?
Niel de Beaudrap
1
Ein Problem hierbei ist, dass wir einen Satz auswählen müssen, für den sich Mitgliedschaftstests in NP befinden. S
Emil
1
Ich habe der Antwort etwas mehr Hintergrund hinzugefügt. Eigentlich ist es mir im Allgemeinen egal, ob die Gruppe auf S einwirkt oder nicht, solange wir antworten können: "Ist diese Permutation ein Automorphismus dieses Graphen?" Bei lateinischen Quadraten können wir dies als Gruppenaktion interpretieren.
Douglas S. Stones

Antworten:

14

Nehmen Sie eine beliebige Sprache (die aus binären Zeichenfolgen besteht). Konstruieren Sie die Menge S von Graphen wie folgt:LS

  • Für jede Saite mit | x | = N , haben wir den Graphen G x = ( V x , E x ) in S , wobei der Satz von Knoten V x = { 1 , 2 , . . . , 3 n } und folgende Kanten: wenn das Bit i von x ist 0 , dann sind die Knoten 3 i - 2 und 3xL|x|=nGx=(Vx,Ex)SVx={1,2,...,3n}ix03i2 sind benachbart, andernfalls sind 3 i - 2 und 3 i benachbart. Es gibt keine anderen Kanten.3i13i23i

Nun wollen wir eine Permutation sein { 1 , 2 , . . . , 3 n } . Es sei angenommen, dass p ein Automorphismus eines Graphen in S ist . Das heißt, p ist eine automorphism von G y für einige y L . Lassen i { 1 , 2 , . . . , n } . Betrachten wir die folgenden zwei Fälle:p{1,2,...,3n}pSpGyyLi{1,2,...,n}

  • , p ( 3 i - 1 ) = 3 i - 2 , p ( 3 i ) = 3 i . Dann müssen wir Bit i von y gleich 0 haben .p(3i2)=3i1p(3i1)=3i2p(3i)=3iiy0
  • , p ( 3 i - 1 ) = 3 i - 1 , p ( 3 i ) = 3 i - 2 . Dann müssen wir Bit i von y gleich 1 haben .p(3i2)=3ip(3i1)=3i1p(3i)=3i2iy1

Wenn wir also die Frage "Ist ein gegebener Automorphismus von etwas G S " lösen können, können wir auch die Frage " Ist eine gegebene Zeichenkette y in L " lösen . Außerdem, wenn wir das erstere in etwa der Polynomzeit in | tun können p | können wir Letzteres in polynomialer Zeit in | tun y | auch.pGSyL|p||y|

Jetzt können Sie einfach zu Ihrem Lieblingsproblem machen. Oder das Halteproblem ...L

Jukka Suomela
quelle
Und um die ursprüngliche Frage tatsächlich zu beantworten: Sei ein NP-vollständiges Problem, und Sie werden ein S haben, so dass das Automorphismusproblem NP-vollständig ist. Das Zertifikat für eine Antwort „ja“ ist ein G yS derart , daß p die automorphism von ist G y sowie das Zertifikat für y L . LSGySpGyyL
Jukka Suomela
5
@Jukka: Eine Möglichkeit, die Frage näher an die ursprüngliche Motivation lateinischer quadratischer Graphen heranzuführen, besteht darin, die Menge von Graphen unter Isomorphismus zu schließen. Dies ist auch eine ganz natürliche Einschränkung. Die Menge S, die Sie aus einer beliebigen Sprache L konstruieren, ist nicht isomorph und in diesem speziellen Sinne etwas unnatürlich. Ich verstehe nicht, wie Sie Ihre Konstruktion ändern können, um diese Einschränkung zu erfüllen, aber ich denke, es wäre sehr interessant, wenn dies möglich wäre. SSL
Joshua Grochow
1
@Joshua: Ich denke, es ist möglich, die Konstruktion wie folgt zu ändern: Sowohl die Graphen als auch die Permutationen, die wir in den Abfragen verwenden, bestehen aus disjunkten Zyklen . Genauer gesagt , enthält einen Zyklus der Länge 2 i + a + 1 genau dann , wenn das Bit i von x ist gleich a . In ähnlicher Weise zu bestimmen , ob y L , eine Permutation konstruieren p , die einen Zyklus der Länge enthält , 2 i + a + 1 genau dann , wenn das Bit i von y ist gleichGx2i+a+1ixayLp2i+a+1iy . (Ich könnte einige Details übersehen haben, aber ich denke, die Grundidee sollte funktionieren ...)a
Jukka Suomela
@Jukka: Schön. Ich glaube, die neue Konstruktion funktioniert wie geschrieben (unter der Annahme, dass nur auf Graphen mit genau n Scheitelpunkten und nicht auf Graphen mit mehr als n Scheitelpunkten einwirkt). pSnnn
Joshua Grochow
pSnnL