En el caso de los gráficos sin etiquetar, el problema del isomorfismo del gráfico puede abordarse mediante una serie de algoritmos que funcionan muy bien en la práctica. Es decir, aunque el peor tiempo de ejecución es exponencial, generalmente se tiene un tiempo de ejecución polinómico.
Esperaba que la situación sea similar en el caso de los gráficos etiquetados. Sin embargo, me resulta muy difícil encontrar alguna referencia que proponga un algoritmo "prácticamente eficiente".
Observación: Aquí, requerimos que el isomorfismo conserve las etiquetas. Es decir, un isomorfismo entre dos términos finitos de álgebra de autómatas / procesos implicaría que los autómatas / términos son esencialmente "iguales al cambio de nombre de los nodos".
La única referencia que encontré fue la de Wikipedia que establece que el problema del isomorfismo de los gráficos etiquetados puede reducirse polinómicamente al de los gráficos ordinarios. Sin embargo, el artículo subyacente trata más sobre teoría de la complejidad que sobre algoritmos prácticos.
Me falta algo, ¿o es realmente el caso de que no hay algoritmos "heurísticos" eficientes para decidir si dos gráficos etiquetados son isomorfos?
Cualquier pista o referencia sería genial.
Respuestas:
Quizás te interese este artículo:
Aidan Hogan: Skolemising Nodos en blanco mientras se preserva el isomorfismo. WWW 2015: 430-440
Tiene un algoritmo (basado en Nauty) para probar el isomorfismo de los gráficos RDF, que son esencialmente gráficos etiquetados dirigidos que pueden contener etiquetas fijas. El algoritmo tiene en cuenta las etiquetas para reducir el espacio de búsqueda.
Si puede representar su gráfico etiquetado de entrada como un gráfico RDF, puede intentar usar el paquete de software asociado "
blabel
" para probar el isomorfismo.fuente
Descubrí que el algoritmo pertenece a la categoría de algoritmos Weisfeiler-Lehman de dimensión k, y falla con los gráficos regulares. Para más aquí:
http://dabacon.org/pontiff/?p=4148
La publicación original sigue:
Hace años, creé un algoritmo simple y flexible para exactamente este problema (isomorfismo gráfico con etiquetas).
Lo llamé "Powerhash", y para crear el algoritmo requirió dos ideas. El primero es el algoritmo del gráfico de iteración de potencia, también utilizado en PageRank. El segundo es la capacidad de reemplazar la función de paso interno de la iteración de potencia con cualquier cosa que queramos. Lo reemplacé con una función que hace lo siguiente en cada iteración y para cada nodo:
En el primer paso, el hash de un nodo se ve afectado por sus vecinos directos. En el segundo paso, el hash de un nodo se ve afectado por el vecindario a 2 saltos de distancia. En el enésimo paso, el hash de un nodo se verá afectado por los N-saltos del vecindario a su alrededor. Por lo tanto, solo necesita continuar ejecutando Powerhash para N = pasos de graph_radius. Al final, el hash del nodo del centro gráfico se habrá visto afectado por todo el gráfico.
Para producir el hash final, clasifique los hashes del nodo del paso final y concatenelos juntos. Después de eso, puede comparar los hashes finales para encontrar si dos gráficos son isomorfos. Si tiene etiquetas, agréguelas (en la primera iteración) en los hashes internos que calcule para cada nodo.
Para más información sobre esto, puede ver mi publicación aquí:
https://plus.google.com/114866592715069940152/posts/fmBFhjhQcZF
El algoritmo anterior se implementó dentro de la base de datos relacional funcional "madIS". Puede encontrar el código fuente del algoritmo aquí:
https://github.com/madgik/madis/blob/master/src/functions/aggregate/graph.py
fuente