Isomorfismo gráfico eficiente para consultas gráficas similares

10

Dado el gráfico G1, G2 y G3, queremos realizar la prueba de isomorfismo F entre G1 y G2, así como entre G1 y G3. Si G2 y G3 son muy similares, de modo que G3 se forma eliminando un nodo e insertando un nodo de G2, y tenemos el resultado de F (G1, G2), ¿podemos calcular F (G1, G3) sin calcularlo desde cero? mediante la ampliación de cualquier método de vanguardia existente?

Por ejemplo, si G2 está formado por los nodos 2,3,4,5 y G3 está formado por los nodos 3,4,5,6, ¿podemos utilizar el resultado de F (G1, G2) para calcular F (G1, G3) más eficientemente?

Eric Huang
fuente
No tengo una discusión en este momento. Pero mi intuición es que su problema está moralmente relacionado con la conjetura de reconstrucción ( en.wikipedia.org/wiki/Reconstruction_conjecture ).
Yixin Cao

Respuestas:

6

Esta es una simple reducción de tiempo polinomial para mostrar que el problema es GI completo : incluso si sabe que G1,G2 son isomorfos, verificando si G3 , construido a partir de G2 eliminando y agregando un nodo, es isomorfo a G1 es tan duro como el isomorfismo gráfico en sí (en el peor de los casos).

Dados dos gráficos G=(V,E),G=(V,E) construir

G1=(VV{u},EE{(vi,u)viV})

es decir, la unión de los dos gráficos más un nodo adicional u conectado a todos los vértices de V

recoger G2=G1 ; y claramente son isomorfos.

Ahora construya G3 eliminando u y agregando u conectado a todos los vértices de V :

G3=(VV{u},EE{(vi,u)viV})

sol1,sol3 son isomorfos sisol,sol son isomorfos.

Marzio De Biasi
fuente
2
Esta es una buena reducción! Sin embargo, agregaría que la completitud GI por sí sola no necesariamente significa que no hay ventaja, solo que en el peor de los casos sus complejidades están polinómicamente relacionadas. Como otro ejemplo, tenga en cuenta que el GI de color de vértice también está completo de GI, pero la mayoría de los algoritmos que conozco aún pueden aprovechar los colores de vértice de una manera útil.
Joshua Grochow
@ JoshuaGrochow: gracias, aclaré ese punto.
Marzio De Biasi
@MarzioDeBiasi: gracias por las explicaciones. Según mi comprensión sobre sus explicaciones, no podemos aprovechar ninguna ventaja para calcular F (G1, G3) conociendo F (G1, G2) si los vértices conectados a u y u 'son diferentes (no necesariamente conectados a todos los vértices de V o V ') incluso si sabemos que G y G' son isomórficos. ¿Es eso correcto? En este caso, ¿es este problema tan difícil como el propio isomorfismo gráfico?
Eric Huang
sol1,sol2sol3sol2sol1,sol3sol3sol1,sol3
Marzio De Biasi
Puede probar el método Weisfeiler-Lehman o sus variaciones, especialmente si sus gráficos originales tienen estructuras como planar, árbol, gráfico de intervalo o gráfico de ancho de árbol acotado, su dimensión Weisfeiler-Lehman es una pequeña constante, en el paso de refinamiento, supongo que puede Aproveche la relación entre los dos gráficos.
Rupei Xu