Niedoskonały izomorfizm subgrafu

Rozważmy następujący problem: Biorąc pod uwagę wykres zapytania i wykres odniesienia G ′ = ( V ′ , E ′ ) , chcemy znaleźć iniekcyjne odwzorowanie f : V → V ′, które minimalizuje liczbę krawędzi ( v 1 , v 2 ) ∈ E taki, że ( f ( v 1 ) , f ( v 2 ) $G = (V, E)$$G' = (V', E')$$f : V \rightarrow V'$$(v_1, v_2) \in E$ . Jest to uogólnienieproblemu izomorfizmu podgrafatu, wktórym pozwalamy, aby podgrafy były izomorficzne do kilku brakujących krawędzi i chcemy znaleźć sposób na zminimalizowanie liczby brakujących krawędzi.$(f(v_1), f(v_2)) \notin E'$

Byłbym również zainteresowany ważoną wersją tego problemu, w której pary wierzchołków przenoszą ciężar w ( v 1 , v 2 ) (który musi wynosić zero, jeśli ( v 1 , v 2 ) ∉ E ) , i podobnie dla G ′ , i chcemy zminimalizować ∑ v 1 , v 2 ( max ( 0 , w ( $(v_1, v_2) \in V^2$$w(v_1, v_2)$$(v_1, v_2) \notin E)$$G'$ ( maksimum służy tylko do karania wag z wykresu zapytań, które są większe niż z wykresu odniesienia).$\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$$\max$

Moje pytanie brzmi: czy ten problem został już zbadany? Czy ma dobrze znaną nazwę? Czy znane są jakieś wydajne algorytmy aproksymacyjne?

Motywacja tego problemu (poza faktem, że wydaje się to naturalną uogólnieniem problemu izomorfizmu podgrafatu) polega na tym, że jest to dobry sposób na przygotowanie planu stołu na imprezę: wykres zapytania to wykres gości z wagami krawędzi reprezentujący zakres, w jakim dwie osoby chcą wchodzić w interakcję, wykres referencyjny ma siedzenia tabel jako wierzchołki i wagi krawędzi wskazujące, w jakim stopniu możliwa jest komunikacja, rozwiązaniem problemu jest mapowanie między ludźmi na siedzenia, które szanuje strukturę społeczną do w jak największym stopniu.

Twoim problemem jest maksymalny problem podgrupy krawędzi wspólnych (Max CES) zdefiniowany w następujący sposób: biorąc pod uwagę dwa wykresy i G ′ , znajdź wykres H z maksymalną liczbą krawędzi, które są izomorficzne dla podrozdziału G i podgrupy G ′ .$G$$G'$$H$$G$$G'$

Dowód : Jesteś znalezienie podgrafu z G izomorficzne do podgrafu z G ' , gdzie | E G | - | E H | jest zminimalizowane. Ponieważ | E G | jest niezmiennikiem G , | E G | - | E H | jest zminimalizowane tylko i tylko wtedy, gdy | E H | jest zmaksymalizowane. Oczywiste jest, że H jest izomorficzny dla podrozdziału G i podgrupy $H$$G$$G'$$|E_{G}| - |E_{H}|$$|E_{G}|$$G$$|E_{G}| - |E_{H}|$$|E_{H}|$$H$$G$ . CO BYŁO DO OKAZANIA$G'$

Przybliżalność W rozprawie doktorskiej Kanna znalazłem opis „nie wiadomo, że można go zbliżyć do stałej” [3] (s. 115). W ostatnim artykule Bahiense i in. [1] wspomniano, że jeśli i | V G ′ | nie muszą być równe, problem staje się trudny do APX. Ale cytatem tego wyniku jest niepublikowana prywatna komunikacja [2].$|V_{G}|$$|V_{G'}|$

1. L. Bahiense, G. Manic, B. Piva, CC de Souza. Maksymalny problem podgrupy krawędzi wspólnej: badanie wielościenne. Pojawi się dyskretna matematyka stosowana. doi: 10.1016 / j.dam.2012.01.026
2. MM Halldorsson, Komunikacja osobista, niepublikowany rękopis, 1994.
3. V. Kann. O zbliżalności problemów optymalizacji NP. Doktorat Teza, raport NADA TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf