Wydajny izomorfizm grafów dla podobnych zapytań grafowych

Biorąc pod uwagę wykres G1, G2 i G3, chcemy wykonać test izomorfizmu F między G1 i G2 oraz G1 i G3. Jeśli G2 i G3 są bardzo podobne, tak że G3 powstaje przez usunięcie jednego węzła i wstawienie jednego węzła z G2, a mamy wynik F (G1, G2), czy możemy obliczyć F (G1, G3) bez obliczania go od zera poszerzając istniejące istniejące metody?

Na przykład jeśli G2 jest utworzony przez węzły 2,3,4,5, a G3 jest utworzony przez węzły 3,4,5,6, czy możemy wykorzystać wynik F (G1, G2) do obliczenia F (G1, G3) bardziej wydajnie?

graph-theory graph-algorithms graph-isomorphism

— Eric Huang
źródło

W tej chwili nie mam kłótni. Ale mam przeczucie, że twój problem jest moralnie związany z hipotezą rekonstrukcji ( en.wikipedia.org/wiki/Reconstruction_conjecture ).

— Yixin Cao

Jest to prosta wielomianowa redukcja czasu, która pokazuje, że problem został zakończony GI : nawet jeśli wiesz, że są izomorficzne, sprawdzanie, czy , zbudowany z usunięciu i dodaniu węzła, jest izomorficzny dla jest tak trudny jak izomorfizm grafu sam (w najgorszym przypadku). $G_1, G_2$ $G_3$ $G_2$ $G_1$

Biorąc pod uwagę dwa wykresy $G = (V, E), G'= (V', E')$ build

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

tj. połączenie dwóch wykresów plus dodatkowy węzeł podłączony do wszystkich wierzchołków $u$ $V$

wybierz ; i wyraźnie są izomorficzne. $G_2 = G_1$

Teraz zbuduj usuwając i dodając połączony ze wszystkimi wierzchołkami : $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ą izomorficzne iff są izomorficzne. $G, G'$

— Marzio De Biasi
źródło

To niezła obniżka! Dodałbym jednak, że sama kompletność oznaczeń geograficznych niekoniecznie oznacza brak korzyści, a jedynie, że w najgorszym przypadku ich złożoność jest wielomianowo powiązana. Jako kolejny przykład zauważ, że GI w kolorze wierzchołka jest również GI-kompletne, ale większość znanych mi algorytmów może nadal wykorzystywać kolory wierzchołków w przydatny sposób.

— Joshua Grochow

@JoshuaGrochow: dzięki, wyjaśniłem ten punkt.

— Marzio De Biasi

@MarzioDeBiasi: dziękuję za wyjaśnienia. W oparciu o moje rozumienie twoich wyjaśnień, nie możemy skorzystać z obliczenia F (G1, G3) znając F (G1, G2), jeśli wierzchołki połączone z u i u są różne (niekoniecznie połączone ze wszystkimi wierzchołkami V lub V '), nawet jeśli wiemy, że G i G' są izomorficzne. Czy to jest poprawne? Czy w takim przypadku ten problem jest tak trudny jak sam izomorfizm wykresu?

— Eric Huang,

@EricHuang: redukcja mówi, że biorąc pod uwagę dwa wykresy izomorficzne i jawny sposób budowania poprzez usunięcie / dodanie jednego węzła (i niektórych krawędzi) do problem sprawdzania, czy są izomorficzne, jest tak trudny jak izomorfizm grafów . BTW, ten wynik rozciąga się również na związany z tym problem obietnicy, w którym nie podano wyraźnego sposobu budowania , ale tylko obietnica, że są izomorficzne aż do operacji usuwania / dodawania węzła.

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,

Możesz wypróbować metodę Weisfeilera-Lehmana lub jej odmiany, zwłaszcza jeśli twoje oryginalne wykresy mają struktury takie jak planar, drzewo, wykres interwałowy lub ograniczony wykres szerokości, ich wymiar Weisfeiler-Lehman jest niewielką stałą, na etapie udoskonalania, myślę, że możesz skorzystać z relacji między dwoma wykresami.

— Rupei Xu