Contraejemplo para el algoritmo eficiente de Corneil para isomorfismo gráfico

16

En el artículo An Efficient Algorithm for Graph Isomorphism de Corneil y Gotlieb, 1970, se estableció una conjetura en la que se basó el algoritmo para resolver GI en el tiempo polinomial. A saber:

que los gráficos representativos exhiben la división de automorfismo del gráfico dado

Obviamente, esta conjetura no está probada hasta ahora (de lo contrario, sabríamos que GI está en P). Mi pregunta es si ya se demostró que era falso y, posiblemente, ¿se dio un contraejemplo?

John D.
fuente

Respuestas:

18

Mathon ha demostrado que la conjetura utilizada por Corneil y Gotlieb es falsa. La primera referencia establece este hecho.

1- P. Foggia, C.Sansone, M. Vento, Una comparación de rendimiento de cinco algoritmos para isomorfismo gráfico, Proc. Tercer taller IAPR-TC15 Representaciones basadas en gráficos en reconocimiento de patrones, 2001, pp. 188-199.

2- R. Mathon, Gráficos de muestra para pruebas de isomorfismo, Congressus Numerantium, 21, pp. 499-517, 1978

Mohammad Al-Turkistany
fuente