Gibt es einen effizienten Algorithmus, um festzustellen, ob ein Graph einen nicht trivialen Automorphismus aufweist oder nicht?

Ich arbeite an einem Problem im Zusammenhang mit lateinischen Quadraten und möchte eine Methode für das, was im Wesentlichen auf das Entscheidungsproblem hinausläuft:

Eingabe : Ein endlicher, einfacher Graph G.
Ausgabe : YESWenn G NOansonsten einen nicht trivialen Automorphismus hat .

Daher...

Frage : Gibt es einen effizienten Algorithmus, um festzustellen, ob ein Graph einen nicht trivialen Automorphismus aufweist oder nicht?

Wir könnten Nauty oder Bliss (und möglicherweise einige andere Pakete) verwenden, um die gesamte Automorphismusgruppe zu berechnen, aber ich brauche sie nicht. Ich muss nur feststellen, ob es trivial ist oder nicht.

Es ist möglich, dass dieses Entscheidungsproblem in seiner Komplexität theoretisch gleichwertig ist, um "die gesamte Automorphismusgruppe zu berechnen". Ich bin mir nicht sicher.

Für meinen Zweck bedeutet "effizient" im Grunde "schneller in der Praxis als die Berechnung der gesamten Automorphismusgruppe", aber ich interessiere mich auch für die Theorie dahinter.

algorithms graphs graph-theory reference-request Rebecca J. Stones
quelle

Dies entspricht dem Graphisomorphismus.

Yuval Filmus

@YuvalFilmus Soweit mir bekannt ist, ist keine Reduktion von "Ist

isomorph zu

" auf "Hat

einen nichttrivialen Automorphismus?" Bekannt. Wenn

dann hat ihre disjunkte Vereinigung offensichtlich einen nichttrivialen Automorphismus (Swap

und

), aber jeder nichttriviale Automorphismus von

wäre auch ein nichttrivialer Automorphismus von

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

G_{1} ≃ G_{2}

$G_1\simeq G_2$

G_{1}

$G_1$

G_{2}

$G_2$

G_{1}

$G_1$

G_{1} + G_{2}

$G_1+G_2$

David Richerby

In Bezug auf Ihre letzte Frage, wenn man GA ein Orakel gibt, kann man in Polynomzeit einen Generatorsatz der Automorphismusgruppe finden, dann ist GI Turing auf GA reduzierbar, was ich nicht sicher bin, ist bekannt.

Ariel

@ DavidRicherby Was ist mit dem folgenden Papier? sciencedirect.com/science/article/pii/…

Yuval Filmus

@YuvalFilmus OK, Sie verwenden also Turing-Reduzierungen und ich verwende viele Reduzierungen. Und ich denke, Turing-Reduzierungen sind für jemanden relevanter, der tatsächlich versucht, das Problem zu lösen.

David Richerby

Da Sie sich auch für die Theorie dahinter interessieren, würde ich Ihnen einen quasi-polynomiellen Zeitalgorithmus für Ihr Problem geben.

Für jedes Paar von Eckpunkten $u\neq v$ (gleichen Grades) in $G$ versuchen wir zu sehen, ob es möglich ist, und zu tauschen . $u$ $v$

Machen Sie dazu eine Kopie von $G$ und nennen Sie es $G'$ . Löschen Sie nun $u$ aus $G$ , löschen Sie (Kopie von) $v$ aus $G'$ .

$w\in N(u)$

$w\in N(copy\ of\ v)$

Alle oben genannten sehr langen, aber polynomiell langen Wege sollten gleich lang sein.

Rufen Sie Babais Algorithmus für die Eingabe dieses neu erstellten Diagrammpaars auf.

$(u, v)$ $YES$ $YES$

$YES$ $NO$

$N(u)$ $N(v)$ $N(u)$ $N(v)$ $YES$ $u$ $v$ $G$ $G'$ $G$

Die Laufzeitkomplexität ist immer noch quasi-poly.

Thinh D. Nguyen
quelle

Gibt es einen effizienten Algorithmus, um festzustellen, ob ein Graph einen nicht trivialen Automorphismus aufweist oder nicht?

Antworten: