¿Alguien sabe de un contraejemplo del algoritmo de isomorfismo gráfico Dharwadker-Tevet?

En http://www.dharwadker.org/tevet/isomorphism/ , hay una presentación de un algoritmo para determinar si dos gráficos son isomorfos. Teniendo en cuenta una serie de afirmaciones "interesantes" de A Dharwadker, no estoy dispuesto a creerlo.

En mi investigación, encuentro que el algoritmo definitivamente producirá la respuesta correcta y le diré que dos gráficos no son isomórficos cuando en realidad es correcto. Sin embargo, no está claro que el algoritmo le diga constantemente si dos gráficos son isomórficos cuando en realidad lo son. La "prueba" de su resultado deja algo que desear.

Sin embargo, no conozco un contraejemplo. Antes de comenzar a escribir software para probar el algoritmo, pensé que vería si alguien ya conocía un contraejemplo.

Alguien solicitó una sinopsis del algoritmo. Haré lo que pueda aquí, pero para entenderlo realmente, debe visitar http://www.dharwadker.org/tevet/isomorphism/ .

El algoritmo tiene dos fases: una fase de "firma" y una fase de clasificación. La primera fase de "firma" (este es mi término para su proceso; lo llaman generar la "matriz de signos") clasifica efectivamente los vértices en diferentes clases de equivalencia. La segunda fase primero ordena los vértices de acuerdo con su clase de equivalencia, y luego aplica un procedimiento de clasificación dentro de las clases de equivalencia para establecer un isomorfismo entre los dos gráficos. Curiosamente, no pretenden establecer una forma canónica para los gráficos; en cambio, un gráfico se usa como una especie de plantilla para el segundo.

La fase de firma es realmente bastante interesante, y no le haría justicia aquí al intentar parafrasearla. Si desea más detalles, le recomiendo seguir el enlace para examinar su fase de firma. La "matriz de signos" generada ciertamente retiene toda la información sobre el gráfico original y luego establece un poco más de información. Después de recopilar las firmas, ignoran la matriz original, ya que las firmas contienen toda la información sobre la matriz original. Baste decir que la firma realiza alguna operación que se aplica a cada borde relacionado con el vértice y luego recolecta el conjunto múltiple de elementos para un vértice para establecer una clase de equivalencia para el vértice.

La segunda fase, la fase de clasificación, es la parte que es dudosa. En particular, esperaría que si su proceso funcionara, entonces el algoritmo desarrollado por Anna Lubiw para proporcionar un "Orden de matrices doblemente léxico" (Ver: http://dl.acm.org/citation.cfm?id=22189 ) También funcionaría para definir una forma canónica para un gráfico.

Para ser justos, no entiendo completamente su proceso de clasificación, aunque creo que hacen un trabajo razonable al describirlo. (Simplemente no he trabajado con todos los detalles). En otras palabras, me puede faltar algo. Sin embargo, no está claro cómo este proceso puede hacer mucho más que encontrar accidentalmente un isomorfismo. Claro, probablemente lo encontrarán con alta probabilidad, pero no con garantía. Si las dos gráficas no son isomorfas, el proceso de clasificación nunca lo encontrará y el proceso rechaza correctamente las gráficas.

Para graphA.txt:

25
 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1
 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1
 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0
 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1
 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0
 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1
 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1
 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0
 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1
 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0
 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0
 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0
 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1
 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1
 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1
 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0

y graphB.txt:

25
 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0
 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0
 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1
 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0
 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1
 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1
 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1
 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0
 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1
 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1
 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0
 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1
 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0
 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0
 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0
 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1
 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1
 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1
 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1
 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0
 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0

que se obtiene graphA.txtaplicando la permutación (aleatoria)

 22 9 24 11 15 8 5 18 13 14 2 10 23 0 3 17 4 16 6 19 7 21 12 1 20

El programa C ++ isororphism.cppde la Figura 6.3. Un programa C ++ para el algoritmo de isomorfismo gráfico en http://www.dharwadker.org/tevet/isomorphism/ ofrece el siguiente resultado:

The Graph Isomorphism Algorithm
by Ashay Dharwadker and John-Tagore Tevet
http://www.dharwadker.org/tevet/isomorphism/
Copyright (c) 2009
Computing the Sign Matrix of Graph A...
Computing the Sign Matrix of Graph B...
Graph A and Graph B have the same sign frequency vectors in lexicographic order but cannot be isomorphic.
See result.txt for details.

Por lo tanto, podemos suponer que este es un contraejemplo del algoritmo de isomorfismo gráfico Dharwadker-Tevet.

Como lo sugirió Bill Province, el problema es

$G_A$$G_B$

La objeción de Bill Province es que la prueba de la Proposición 4.1. no utiliza ninguna propiedad especial de la matriz de signos que no se aplique también a la matriz de adyacencia. Más precisamente, el siguiente paso en la prueba es incorrecto:

$1, ..., t$$A$$B$$1, ..., t$$A$$v_1, ..., v_t$$1, ..., t$$B$$φ(v_1) = v'_1, ..., φ(v_t) = v'_t$ respectivamente.

porque incluso si las filas han coincidido perfectamente, no se sigue que las etiquetas de vértice coincidan con las etiquetas dadas por cualquier isomorfismo .$φ$

Debido a que se identificó un agujero en la prueba de corrección, el contraejemplo anterior debería ser suficiente para refutar la corrección alegada del algoritmo propuesto.

Agradecimientos El contraejemplo es el primero de los octavos pares de gráficos de

http://funkybee.narod.ru/graphs.htm

Para manipular gráficos, utilicé y modifiqué el código fuente de ScrewBoxR1160.tar que se encuentra en

https://people.mpi-inf.mpg.de/~pascal/software/

Para comprender el agujero en la prueba de corrección, el comentario de András Salamon sobre Weisfeiler-Lehman fue muy útil, al igual que las explicaciones de

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

Vzn proporcionó la motivación para usar esta pregunta como una oportunidad para familiarizarse con la náutica / Traces y los aspectos prácticos del isomorfismo gráfico. El beneficio de aprender a usar programas de última generación para los isomorfismos de gráficos hizo que valiera la pena dedicar algo de tiempo para encontrar un contraejemplo (que creía firmemente que existía).