Existe-t-il un algorithme efficace pour déterminer si un graphe a un automorphisme non trivial?

Je travaille sur un problème lié aux carrés latins, et je veux une méthode pour ce qui se résume essentiellement au problème de décision:

Entrée : Un graphe fini et simple G.
Sortie : YESsi G a un automorphisme non trivial, NOsinon.

Par conséquent...

Question : Existe-t-il un algorithme efficace pour déterminer si un graphe présente ou non un automorphisme non trivial?

Nous pourrions utiliser Nauty ou Bliss (et éventuellement d'autres packages) pour calculer l'ensemble du groupe d'automorphisme, mais je n'en ai pas besoin; tout ce que je dois déterminer, c'est si c'est trivial ou non.

Il est possible que ce problème de décision soit théoriquement équivalent en complexité pour «calculer l'ensemble du groupe d'automorphisme» d'une manière ou d'une autre. Je ne suis pas sûr.

Dans mon but, «efficace» signifie essentiellement «plus vite dans la pratique que le calcul de l'ensemble du groupe d'automorphisme», mais je m'intéresse également à la théorie derrière.

algorithms graphs graph-theory reference-request Rebecca J. Stones
la source

Cela équivaut à l'isomorphisme du graphe.

Yuval Filmus

@YuvalFilmus Pour autant que je sache, il n'y a pas de réduction connue de "Is isomorphic to " to "Does have a nontrivial automorphism." Évidemment, si alors leur union disjointe a un automorphisme non trivial (échange et ) mais tout automorphisme non trivial de serait également un automorphisme non trivial de .

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

Concernant votre dernière question, si on donne un oracle à GA, on peut, en temps polynomial, trouver un groupe électrogène du groupe d'automorphisme, alors GI est Turing réductible à GA, dont je ne suis pas sûr.

Ariel

@DavidRicherby Qu'en est-il de l'article suivant? sciencedirect.com/science/article/pii/…

Yuval Filmus

@YuvalFilmus OK, vous utilisez donc des réductions de Turing et j'utilise plusieurs réductions. Et je suppose que les réductions de Turing sont plus pertinentes pour quelqu'un qui essaie réellement de résoudre le problème.

David Richerby

Réponses:

Puisque vous êtes également intéressé par la théorie derrière elle, je vous donnerais un algorithme de temps quasi-polynomial pour votre problème.

Pour chaque paire de sommets (de même degré) dans , nous essayons de voir s'il est possible d' échanger et . $u\neq v$ $G$ $u$ $v$

Pour ce faire, faites une copie de , appelez-la . Maintenant, supprimez de , supprimez (copie de) de . $G$ $G'$ $u$ $G$ $v$ $G'$

Ensuite, pour chaque attachez-lui un chemin très long, mais seulement polynomialement long . $w\in N(u)$

Ensuite, pour chaque (copie de) attachez-lui un chemin très long, mais uniquement polynomial . $w\in N(copy\ of\ v)$

Tout le chemin très long mentionné ci-dessus, mais polynomialement long , devrait être de la même longueur.

Appelez l'algorithme de Babai sur l'entrée de cette nouvelle paire de graphiques.

Si pour n'importe quelle paire , nous avons une réponse de Babai, répondez et arrêtez. $(u, v)$ $YES$ $YES$

Si aucun ne renvoie une réponse , répondez et arrêtez. $YES$ $NO$

Clairement, l'attachement à tous les sommets de et force l'isomorphisme graphique du mécanisme de fonctionnement interne de Babai de son algorithme à mapper uniquement les sommets de à . Ainsi, si la réponse est Babai nous pouvons brancher en toute sécurité dans le dos et d'avoir un automorphisme non trivial de , puisque est une copie de . $N(u)$ $N(v)$ $N(u)$ $N(v)$ $YES$ $u$ $v$ $G$ $G'$ $G$

La complexité d'exécution est encore quasi-poly.

Thinh D. Nguyen
la source