Algoritmo de canonización gráfica simple

8

Estoy buscando un algoritmo que proporcione una cadena canónica para un gráfico de color dado. Es decir. un algoritmo que devuelve una cadena para un gráfico, de modo que dos gráficos obtienen la misma cadena si y solo si son isomórficos.

En particular, estoy buscando un algoritmo simple que sea fácil de implementar con un rendimiento razonable en la mayoría de los gráficos (por supuesto, superpolinomio en el peor de los casos). Espero gráficos pequeños, por lo que el rendimiento no tiene que ser estelar, solo lo suficientemente bueno.

Desafortunadamente, la mayoría de las cosas que he encontrado son muy complejas y están más interesadas en expresar conexiones matemáticas profundas que simplemente describir el algoritmo. Me temo que no tengo tiempo para sumergirme tan profundo. ¿Alguien puede darme un atajo?

Espero algo como el algoritmo Floyd-Warshall. No es óptimo, pero es lo suficientemente bueno y fácil de implementar.

algorithms graph-theory combinatorics Peter
fuente
¿Están las gráficas etiquetadas consistentemente? En caso afirmativo, simplemente escriba todos los bordes y ordene la lista.
adrianN
Oh, lo siento. Los vértices y los bordes están etiquetados, pero no de forma exclusiva. Cada etiqueta puede aparecer varias veces. Supongo que la frase matemática es "coloreada" en lugar de etiquetada. Editaré la pregunta.
Peter
"NP en el peor de los casos, por supuesto", solo para que quede claro: existe un algoritmo de tiempo polinomial (determinista) conocido para el isomorfismo gráfico, por lo que lo mejor que puede esperar es una solución súper polinomial. Y sí, el problema está en NP. Vea aquí para más detalles sobre estas nociones.
Raphael
@Raphael Tienes razón, una terminología más inexacta. El peor caso es el superpolinomio. Sin embargo, existen algoritmos polinomiales de caso promedio, por lo que al menos deberían ser alcanzables.
Peter
@Raphael Lo mejor que puede esperar es un algoritmo rápido que funcione para la mayoría de los gráficos.
Yuval Filmus

Respuestas:

3

Brendan McKay y Adolfo Piperno han escrito una encuesta sobre esta pregunta en 2013. Presentan varios programas de computadora eficientes que canonizan muchos gráficos más rápido de lo que imagina. No es necesario (y no tiene sentido) implementar estos algoritmos usted mismo: están disponibles en línea, incluso como código fuente.

Yuval Filmus
fuente
Hay una reducción entre el GI coloreado y el GI (con un aumento multiplicativo constante dado un número constante de colores), o quizás los algoritmos mismos podrían modificarse.
Yuval Filmus
¿Puedes describir uno aquí para dar una respuesta completa?
Raphael
3
Para cada color, agregue un vértice adicional. Conecte cada vértice original al vértice que representa su color agregando un borde. Asegúrese de que los grados de los vértices de "color" sean únicos; si este no es el caso, agregue bucles u otros bordes falsos. Por cierto, estoy menos que contento con el trabajo de la encuesta McKay / Piperno: es una encuesta de su propia investigación, y las comparaciones que hacen con otras herramientas están en los puntos de referencia que consideran interesantes. Omiten importantes desarrollos recientes y casi todos los puntos de referencia derivados de aplicaciones no teóricas, lo que afecta los resultados empíricos.
Igor Markov
2

Terminé implementando el algoritmo Nauty, pero al hacerlo, descubrí una respuesta a mi propia pregunta. Nauty extiende este algoritmo básico con muchas heurísticas complicadas:

Dados unos pequeños gráficos G de longitud n:

  1. Bucle sobre todopermutaciones de sus vértices.n!
  2. Genere una representación de cadena de cada uno (uno a uno).
  3. Defina un orden canónico de cadenas y recuerde la cadena más pequeña encontrada.

Este algoritmo es , Pero para gráficos pequeños debería funcionar bien.O(n!)

Nauty amplía este algoritmo principalmente mediante la poda del espacio de búsqueda de gráficos a tener en cuenta al buscar el que tiene la representación de cadena más pequeña.

Peter
fuente
1
Los gráficos deben ser realmente pequeños si este enfoque de fuerza bruta es plausible. Inclusoes mayor que . 15!1012
David Richerby
1
@DavidRicherby Absolutamente. Sin embargo, hay casos de uso, como el análisis de motivos, donde esta operación solo se realiza en gráficos de tamaño 3 o 4. De hecho, no sé si se puede encontrar un subgrafo isomorfo canónico en un tiempo razonable para los gráficos. más de 15 nodos (incluso si ahora se sabe que el isomorfismo del subgrafo está muy cerca del polinomio)
Peter