Isomorfismo gráfico eficiente para consultas gráficas semelhantes

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?

graph-theory graph-algorithms graph-isomorphism 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

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). $G_1, G_2$ $G_3$ $G_2$ $G_1$

Dado dois gráficos compilação $G = (V, E), G'= (V', E')$

$G_1 = ( V \cup V' \cup \{u\},\; E \cup E' \cup \{ (v_i,u) \mid v_i \in V \})$

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

escolha ; e claramente eles são isomórficos. $G_2 = G_1$

Agora construa excluindo e adicionando conectado a todos os vértices de : $G_3$ $u$ $u'$ $V'$

$G_3 = ( V \cup V' \cup \{u'\},\; E \cup E' \cup \{ (v_i',u') \mid v_i' \in V'\} )$

$G_1, G_3$ são isomórficos se são isomórficos. $G, G'$

Marzio De Biasi
fonte

Esta é uma boa redução! No entanto, eu acrescentaria que a completude GI sozinha não significa necessariamente que não há 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

G_{1}, G_{2}

$G_1, G_2$

G_{3}

$G_3$

G_{2}

$G_2$

G_{1}, G_{3}

$G_1, G_3$

G_{3}

$G_3$

G_{1}, G_{3}

$G_1,G_3$

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

Isomorfismo gráfico eficiente para consultas gráficas semelhantes

Respostas: