Te equivocas al afirmar que no existe un algoritmo conocido para el isomorfismo de grafos. Hay un algoritmo obvio: dados los grafos $G$ y $H$ con el mismo número de vértices, enumerar todos los posibles mapeos biyectivos desde los vértices de $G$ a los vértices de $H$ y luego comprobar (en $O(v^2)$ tiempo) para ver si cada mapeo es un isomorfismo. Se garantiza que este algoritmo termina; tiene un tiempo de ejecución $O(v!v^2)$ .
Sin embargo, según tengo entendido, la importancia teórica de este problema es que se sospecha que NP-intermedio (NPI). Es decir:
- Está claramente en NP. (El NTM adivina un posible isomorfismo y luego lo comprueba en tiempo polinómico)
- Se sospecha que no sea NP-completo
- Se sospecha que no para estar en P.
La existencia de un problema NPI es equivalente a P!=NP, por lo que los problemas NPI son interesantes al menos por esta razón.
Garey y Johnson dan las siguientes razones para sospechar que el isomorfismo de grafos podría ser NPI:
Los investigadores que han intentado demostrar que el ISOMORFISMO GRÁFICO es NP-completo han observado que su naturaleza es mucho más restringida que la de un problema NP-completo típico, como el ISOMORFISMO SUBGRÁFICO. Las pruebas de NP-completo parecen requerir un poco de libertad de acción; si la estructura deseada $X$ (subconjunto, permutación, programa, etc.) existe, debería seguir existiendo aunque se alteren localmente ciertos aspectos de la instancia. Por ejemplo, una función $f$ será un isomorfismo entre un gráfico $H$ y un subgrafo de un gráfico $G$ incluso si añadimos aristas a $G$ o eliminar los bordes que no están en la imagen de $f$ . Sin embargo, si $f$ es un isomorfismo entre $H$ y $G$ mismo, entonces cualquier cambio en $G$ debe reflejarse en un cambio correspondiente en $H$ o bien $f$ ya no será un isomorfismo. En otras palabras, las pruebas de NP-completitud parecen requerir una cierta cantidad de redundancia en el problema objetivo, una redundancia que GRAPH ISOMORPHISM carece. Desgraciadamente, esta falta de redundancia tampoco parece ser de mucha ayuda en el diseño de un algoritmo de tiempo polinómico para el GRAPH ISOMORPHISM, por lo que quizás pertenezca a NPI.
( Los ordenadores y la intratabilidad (páginas 155-156)
En cambio, el subgrafo Se sabe que el problema del isomorfismo es NP-completo. Es el problema de decidir, dados los grafos $G$ y $H$ , ya sea $G$ es isomorfo a algún subgrafo de $H$ . Una solución eficiente a este problema resuelve obviamente Clique, Maximal Independent Set, Hamiltonian Cycle y otros problemas similares.
2 votos
Dudo que las respuestas aquí aporten mucho más que lo que dice el artículo de la wikipedia. es.wikipedia.org/wiki/Problema de isomorfismo gráfico