Test de l'isomorphisme des graphes asymétriques

13

En lisant les questions exemples où l'unicité de la solution permet de trouver plus facilement , une nouvelle (? Plus facile) question est venue à l' esprit: en fait , nous ne savons pas si le graphique Isomorphisme ( problème) est dans P .gjeP

Mais que se passe-t-il si nous supposons que et G 2 sont asymétriques (c'est-à-dire que les deux n'ont que l'automorphisme trivial (identité))? Le problème devient-il plus facile (temps polynomial)? g1g2

Remarque: le problème ne peut pas être plus difficile que Graph Automorphism ( ), car il y a une réduction rapide: utilisez simplement G A sur G 1 ∪ G 2 , si la réponse est oui, les deux graphiques sont isomorphes (voir aussi Johannes Köbler, Uwe Schöning, Jacobo Torán: l' isomorphisme du graphique est faible pour PP . 401-411).gUNEgUNEg1∪g2

reference-request graph-isomorphism Marzio De Biasi
la source
2
Avec une probabilité approchant 1 lorsque n augmente, votre graphique n'a que l'automorphoisme trival par complexité de Kolmogorov.
Chad Brewbaker
1
gUNE
4
Ce problème est connu sous le nom de problème d'isomorphisme de graphe rigide. Si elle peut être résolue en temps polynomial ou non est largement ouverte. Certains travaux tentent de l'attaquer via des algorithmes quantiques, par exemple, en le réduisant au problème de décalage caché ( arxiv.org/abs/quant-ph/0510185 ), mais les résultats sont généralement négatifs montrant que les techniques essayées ne le font pas. travail.
Mateus de Oliveira Oliveira
1
Il est possible de rigidifier n'importe quel graphe pour qu'il ne comporte qu'un seul endomorphisme (et donc automorphisme), en attachant des graphes rigides entre eux à chaque sommet. Cela implique une réduction de Turing de l'IG à l'isomorphisme décisif des graphes asymétriques. Hélas, ce n'est pas polynomial.
András Salamon
1
Eh bien, Childs / Wocjan ne sont pas les seuls à utiliser rigide pour désigner des graphiques avec un seul automorphisme. Il y a une enquête de Babai de 1994 qui indique déjà que la terminologie n'est pas cette norme www.cs.uchicago.edu/~laci/handbook/handbookchapter27.pdf. Toujours dans les temps modernes, il a été utilisé dans ce sens par Jacobo Toran ( uni-ulm.de/fileadmin/website_uni_ulm/.../toran/hard.pdf ). Il semble donc qu'il s'agisse de savoir si l'auteur se soucie ou non des plongements. Mais j'ai utilisé asymétrique dans ma réponse pour éviter toute confusion.
Mateus de Oliveira Oliveira

Réponses:

11

À la demande de Marzio De Biasi, je transforme mon commentaire en réponse.

Un graphique est asymétrique (certains auteurs le qualifient de rigide) s'il a un automorphisme unique, c'est-à-dire l'identité. Comme l'a souligné Chad Brewbacker, la plupart des graphiques sont asymétriques. Cependant, les deux questions suivantes sont ouvertes:

1) L'isomorphisme des graphes asymétriques est-il dans P?

2) L'isomorphisme des graphes généraux peut-il être réduit à l'isomorphisme des graphes asymétriques?

Ω(nJournal⁡n)

Mateus de Oliveira Oliveira
la source