Historia i status problemu z dopasowaniem wykresu

Częścią trudności w znalezieniu więcej informacji na temat tego problemu jest to, że problem z dopasowaniem wykresu różni się od jego znacznie bardziej znanego kuzyna, problemu z dopasowywaniem, ale trudno go od niego odróżnić podczas korzystania z wyszukiwarek.

Biorąc pod uwagę dwa wykresy i takie, że, zadaniem jest znalezienie bijection tak aby ten bijection ustalił jak najwięcej korespondencji między krawędziami i jak to możliwe.G ′ = ( V ′ , E ′ ) | V | = | V ′ | π : V → V ′ G G $G=(V,E)$$G'=(V',E')$$|V| = |V'|$$\pi : V \rightarrow V'$$G$$G'$

Innymi słowy, jeśli i są macierzami przylegania, to chcemy zmaksymalizowaćM $M$$M'$

$\sum_{v,w \in V} M_{v,w} \cdot M'_{\pi(v),\pi(w)}$

Ten problem wyraźnie zawiera izomorfizm grafów jako szczególny przypadek i można go zredukować do dopasowania dwustronnego z redukcją (nie wielomianową!).

Jakie rodzaje algorytmów istnieją i co wiadomo o ich złożoności?

Z pracy Przybliżony izomorfizm wykresu :

Badamy optymalizacyjne wersje Graph Isomorphism. Biorąc pod uwagę dwa wykresy , jesteśmy zainteresowani znalezieniem z do który maksymalizuje liczbę dopasowań (krawędzie odwzorowane na krawędzie lub nie-krawędzie zmapowane na nie-krawędzie). Podajemy schemat aproksymacji czasu , który dla dowolnego stałego współczynnika oblicza aproksymację . Udowadniamy to, łącząc$G_1,G_2$ V ( G 1 ) V ( G 2 ) n O ( log n ) α < 1 α n O ( log n$π$$V(G_1)$$V(G_2)$$n^{O(\log{n})}$$α < 1$$α$$n^{O(\log{n})}$algorytm aproksymacji błędu addytywności czasowej według Arora i in. [Matematyka. Program., 92, 2002] z prostym algorytmem uśredniania. Bierzemy również pod uwagę odpowiedni problemu minimalizacji (niedopasowania) i udowodnić, że jest NP-trudne do -approximate dla każdego czynnika stała . Ponadto pokazujemy, że NP jest trudne do przybliżenia maksymalnej liczby krawędzi odwzorowanych na krawędzie powyżej współczynnika wynoszącego 0,94.$α$$α$

Nie mam pojęcia o twoim problemie. Ale zdarza mi się, że znam świetny (najszerszy) zbiór artykułów dotyczących algorytmów dopasowywania wykresów w PDFS . Oklaski dla Setha Pettiego!

Artykuł, który @Austin Buchanan wskazał powyżej na temat przybliżonego izomorfizmu grafów, nie wydaje się odpowiadać żądanej wersji. Zakładam, że macierz przylegania ma wpisów, w którym to przypadku cel mierzy tylko dopasowane krawędzie. Przybliżony model wykresu izomorfizmu mierzy zarówno dopasowane niedopasowane krawędzie, co czyni to nieco łatwiejszym z przybliżonego punktu widzenia.$0,1$

Wygląda na to, że zadany problem jest co najmniej tak samo trudny jak problem -densena-podgrafu, który obecnie dopuszcza jedynie przybliżenie wielomianowe. Zobacz http://arxiv.org/abs/1001.2891 i http://arxiv.org/abs/1110.1360, aby uzyskać więcej szczegółów i aktualny status pod względem algorytmów i twardości.$k$

Teraz redukcja. Załóżmy, że chcemy rozwiązać problem -densse-subgrafu na wykresie ; to znaczy chcemy znaleźć podzbiór węzłów który maksymalizuje liczbę krawędzi na indukowanym wykresie . Można zmniejszyć to do problemu poprzez ustawienie być wykres składający się z kliki na -vertices i izolowanych wierzchołków, a jest ustawiona na .H k S G [ S ] G k n - k G ′$k$$H$$k$$S$$G[S]$$G$$k$$n-k$$G'$$H$