Znalezienie dopasowania, którego skurcz minimalizuje liczbę łuków na wykresie

Biorąc pod uwagę mieszany wykres z krawędziami i łukami , znajdź dopasowanie w które minimalizuje liczbę łuków w , gdzie jest uzyskiwane z przez kurczenie dopasowanych wierzchołków i usuwanie łuki równoległe.E A E G / M G / M $G=(V,E,A)$$E$$A$$E$$G/M$$G/M$$G$

Czy (wersja decyzyjna) ten problem NP jest kompletny? Czy zostało to zbadane w literaturze?

Nie wiem, czy masz zamiar pozwolić, aby nieukierowane krawędzie w E i łuki w A były równoległe, czy nie, ale na końcu to nie ma znaczenia. W tej odpowiedzi zakładamy, że nie zezwalasz na równoległe krawędzie i łuki.

Rozważmy przypadek szczególny, gdzie dla każdego łuku w A , zawiera również po łuku w kierunku przeciwnym. W takim przypadku możemy zignorować orientację łuków i uznać je za niedokierowane. Nazywamy krawędzie E czarne krawędzie i krawędzie w A czerwony krawędzie .

Nawet pod tymi dwoma ograniczeniami problem jest NP-zupełny dzięki redukcji z Max-2SAT. Niech φ być wzór 2CNF w n zmiennych z m punktach. Skonstruuj wykres G z 3 n wierzchołkami v 1 , … , v n , x 1 , … , x n , ˉ x 1 , … , ˉ x n w następujący sposób. G ma 2$x_1,\dots,x_n$$v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$n czarne krawędzie: oraz ( v i , ˉ x i ) dla i = 1,…, n . G ma czerwone krawędzie. Najpierw połącz i dla i ≠ j czerwoną krawędzią. Następnie, dla każdej odrębnej zmiennej i , rozważmy cztery pary literałów . Połącz literały$(v_i,x_i)$$(v_i,\bar{x}_i)$$5\binom{n}{2}-m$v j x i x j ( l , l ′ ) = ( x i , x j ) , ( x i , ˉ x j ) , ( ˉ x i , x j ) , ( ˉ x i , ˉ x j ) l l ′ ( ˉ l ∨ ˉ l ′$v_i$$v_j$$x_i$$x_j$$(l,l')=(x_i,x_j),(x_i,\bar{x}_j),(\bar{x}_i,x_j),(\bar{x}_i,\bar{x}_j)$$l$i czerwoną krawędzią wtedy i tylko wtedy, gdy klauzula nie pojawia się w φ .$l'$$(\bar{l}\vee\bar{l}')$

Oczywiste jest, że musimy brać pod uwagę maksymalne dopasowania w czarnych krawędziach, aby zminimalizować liczbę czerwonych krawędzi po skurczeniu. Oczywiste jest również, że każde maksymalne dopasowanie M w czarnych krawędziach składa się z n krawędzi łączących z dla i = 1,…, n . Zidentyfikuj to maksymalne dopasowanie M z przypisaniem prawdy . Łatwo jest zweryfikować, że po skurczeniu M i usunięciu równoległych krawędzi, wykres ma dokładnie czerwone krawędzie, gdzie kl i ∈ { x i , ˉ x i } { l 1 , … , l n } 4 ($v_i$$l_i\in\{x_i,\bar{x}_i\}$$\{l_1,\dots,l_n\}$$4\binom{n}{2}-k$jest liczbą klauzul spełnianych przez to przypisanie prawdy. Dlatego minimalizacja liczby czerwonych krawędzi po skurczeniu dopasowania w czarnych krawędziach jest równoważna maksymalizacji liczby spełnionych klauzul.