Isomorfismo gráfico eficiente para consultas gráficas semelhantes

10

Dado o gráfico G1, G2 e G3, queremos realizar o teste de isomorfismo F entre G1 e G2, bem como G1 e G3. Se G2 e G3 são muito semelhantes, de modo que G3 é formado pela exclusão de um nó e pela inserção de um nó de G2, e temos o resultado de F (G1, G2), podemos calcular F (G1, G3) sem computá-lo do zero estendendo qualquer método de ponta existente?

Por exemplo, se G2 é formado pelos nós 2,3,4,5 e G3 é formado pelos nós 3,4,5,6, podemos usar o resultado de F (G1, G2) para calcular F (G1, G3) com mais eficiência?

Eric Huang
fonte
Eu não tenho uma discussão neste momento. Mas meu pressentimento é que seu problema está moralmente relacionado às conjecturas de reconstrução ( en.wikipedia.org/wiki/Reconstruction_conjecture ).
Yixin Cao

Respostas:

6

Esta é uma redução de tempo polinomial simples para mostrar que o problema é GI completo : mesmo se você souber que são isomórficos, verifique se , construído a partir de excluindo e adicionando um nó, é isomórfico para é tão difícil quanto o isomorfismo do gráfico em si (no pior dos casos).G1,G2G3G2G1

Dado dois gráficos compilaçãoG=(V,E),G=(V,E)

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

ou seja, a união dos dois gráficos mais um nó extra conectado a todos os vértices deuV

escolha ; e claramente eles são isomórficos.G2=G1

Agora construa excluindo e adicionando conectado a todos os vértices de :G3uuV

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

G1,G3 G , G são isomórficos se são isomórficos.G,G

Marzio De Biasi
fonte
2
Esta é uma boa redução! No entanto, eu acrescentaria que a completude GI sozinha não significa necessariamente que não vantagem, apenas que, na pior das hipóteses, suas complexidades estão relacionadas polinomialmente. Como outro exemplo, observe que a IG colorida de vértice também é completa, mas a maioria dos algoritmos que conheço ainda pode tirar proveito das cores dos vértices de uma maneira útil.
Joshua Grochow
@ JoshuaGrochow: obrigado, esclareci esse ponto.
Marzio De Biasi
@MarzioDeBiasi: obrigado pelas explicações. Com base no meu entendimento sobre suas explicações, não podemos tirar vantagem de calcular F (G1, G3) sabendo que F (G1, G2) se os vértices conectados a u e u 'são diferentes (não necessariamente conectados a todos os vértices de V ou V ') mesmo se soubermos que G e G' são isomórficos. Isso está correto? Nesse caso, esse problema é tão difícil quanto o próprio isomorfismo do gráfico?
Eric Huang
G1,G2G3G2G1,G3G3G1,G3
Marzio De Biasi
Você pode tentar o método Weisfeiler-Lehman ou suas variações, especialmente se os gráficos originais tiverem estruturas como planar, árvore, gráfico de intervalo ou gráfico de largura da árvore limitada, a dimensão Weisfeiler-Lehman é uma constante pequena, na etapa de refinamento, acho que você pode tire proveito da relação entre os dois gráficos.
Rupei Xu 29/07/19