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

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.

cc.complexity-theory graph-theory np-hardness automorphism 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

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

Ein Problem hierbei ist, dass wir einen Satz

auswählen müssen, für den sich Mitgliedschaftstests in NP befinden.

S

$S$

Emil

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:

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

Für jede Saite mit , haben wir den Graphen in , wobei der Satz von Knoten und folgende Kanten: wenn das Bit von ist , dann sind die Knoten und $x \in L$ $|x| = n$ $G_x = (V_x,E_x)$ $S$ $V_x = \{1,2,...,3n\}$ $i$ $x$ $0$ $3i-2$ sind benachbart, andernfalls sind und benachbart. Es gibt keine anderen Kanten. $3i-1$ $3i-2$ $3i$

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

, , . Dann müssen wir Bit von gleich . $p(3i-2) = 3i-1$ $p(3i-1) = 3i-2$ $p(3i) = 3i$ $i$ $y$ $0$
, , . Dann müssen wir Bit von gleich . $p(3i-2) = 3i$ $p(3i-1) = 3i-1$ $p(3i) = 3i-2$ $i$ $y$ $1$

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

so dass das Automorphismusproblem NP-vollständig ist. Das Zertifikat für eine Antwort „ja“ ist ein

derart , daß

die automorphism von ist

sowie das Zertifikat für

L

$L$

S

$S$

G_{y} \in S

$G_y \in S$

p

$p$

G_{y}

$G_y$

y \in L

$y \in L$

Jukka Suomela

@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

Sie aus einer beliebigen Sprache

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.

S

$S$

S

$S$

L

$L$

Joshua Grochow

@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

genau dann , wenn das Bit

von

ist gleich

. In ähnlicher Weise zu bestimmen , ob

, eine Permutation konstruieren

, die einen Zyklus der Länge enthält ,

genau dann , wenn das Bit

von

ist gleich

G_{x}

$G_x$

2 i + a + 1

$2i+a+1$

i

$i$

x

$x$

a

$a$

y \in L

$y \in L$

p

$p$

2 i + a + 1

$2i+a+1$

i

$i$

y

$y$

. (Ich könnte einige Details übersehen haben, aber ich denke, die Grundidee sollte funktionieren ...)

a

$a$

Jukka Suomela

@Jukka: Schön. Ich glaube, die neue Konstruktion funktioniert wie geschrieben (unter der Annahme, dass

nur auf Graphen mit genau

Scheitelpunkten und nicht auf Graphen mit mehr als

Scheitelpunkten einwirkt).

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

Joshua Grochow

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$