Problema de l'isomorfisme de grafos

El problema de l'isomorfisme gràfic és el problema computacional per a determinar si dos gràfics finitos són isomòrfics.

No se sap que el problema es puga resoldre en temps polinomial ni que siga NP-complet i, per lo tant, pot estar en la classe de complexitat computacional NP-intermija. Se sap que el problema d'isomorfisme gràfic està en la'jerarquia baixa de la classe NP, lo que implica que no és NP complet a menos que la jerarquia de temps polinomial colapse al seu segon nivell. Al mateix temps, l'isomorfisme per a moltes classes especials de gràfics es pot resoldre en temps polinomial, i en la pràctica l'isomorfisme gràfic a sovint es pot resoldre de manera eficient.

Este problema és un cas especial del problema d'isomorfisme subgráfico' que pregunta si un gràfic donat G conté un subgráfico que és isomorfo a un atre gràfic donat H i que se sap que és NP-complet. També se sap que és un cas especial del problema del subgrup amagat no abeliano sobre el grup simètric.

En l'àrea de reconeiximent d'imàgens es coneix com la coincidència gràfica exacta.

Estat de l'art

El millor algoritme teòric actualment acceptat es deu a Babai i Luks (1983), i es basa en el treball anterior de Luks (1982) combinat en un algoritme subfactorial de V. N. Zemlyachenko (Zemlyachenko, Korneenko i Tyshkevich 1985). L'algoritme ha eixecutat el temps 2^{O(√n log n)} per a gràfics en n vèrtiços i es basa en la classificació de grups finitos simples. Sense CFSG, László Babai (1980) va obtindre primer un llímit 2^{O (√n log2 n)} llaugerament més dèbil, i Babai & Luks (1983) ho va estendre als gràfics generals. La millora de l'exponent √n és un gran problema obert; per a gràfics fortament regulars açò va ser fet per Spielman (1996). Para hipergrafos de ranc llimitat, Babai i Codenotti (2008) varen obtindre un llímit superior subexponencial que coincidix en el cas dels gràfics.

En novembre de 2015, Babai va anunciar un algoritme de temps quasipolynomial per a tots els gràfics, és dir, un en temps d'eixecució $2^{O((\log n{)}^c)}$ per a alguns arreglats $c>0$ . El 4 de giner de 2017, Babai es va retractar del reclam cuasi-polinomial i va declarar un llímit de temps sub-exponencial en el seu lloc despuix d'Harald Helfgott va descobrir un defecte en la prova. El 9 de giner de 2017, Babai va anunciar una correcció (publicada en la seua totalitat el 19 de giner) i va restaurar el reclam cuasi polinomial, en Helfgott confirmant la solució. Helfgott afirma ademés que un pot prendre c = 3, per lo que el temps d'eixecució és 2^{O((log n) 3)}. La nova prova encara no ha segut revisada per complet.

Existixen varis algoritmes pràctics competitius per a l'isomorfisme gràfic, com els deguts a McKay (1981), Schmidt i Druffel (1976) i Ullman (1976). Si be semblen funcionar be en gràfics aleatoris, una desventaja important d'estos algoritmes és el seu rendiment de temps exponencial en el pijor dels casos.

El problema d'isomorfisme gràfic és computacionalment equivalent al problema de calcular el grup d'automorfisme d'un gràfic, i és més dèbil que el problema d'isomorfisme del grup de permutació i el problema d'intersecció del grup de permutació. Per als últims dos problemes, Babai, Kantor i Luks (1983) varen obtindre llímits de complexitat similars als de l'isomorfisme gràfic.

Casos especials resolts

Varis casos especials importants del problema de l'isomorfisme gràfic tenen solucions eficients de temps polinomial:

• Arbres

• Gràfics plans (De fet, l'isomorfisme gràfic pla està en el espai de registre, una classe continguda en P)

• Gràfics d'interval

• Gràfics de permutació

• Gràfics circulares

• Gràfics de paràmetros acotats

• Gràfics d'ample d'arbre delimitat

• Gràfics del genus delimitat (Nota: els gràfics plans són gràfics del gènero 0)

• Gràfics de grau llimitat

• Gràfics en multiplicitat de autovalores acotada

• k-Gràfics contractibles (una generalisació de grau llimitat i gènero acotat)

• L'isomorfisme de conservació del color dels gràfics de colors en multiplicitat de colors delimitats (és dir, com molt k vèrtiços tenen el mateix color per a un k fix) està en la classe NC, que és una subclasse de P