Dodaj dopasowanie do ścieżki hamiltonianu, aby zmniejszyć maksymalną odległość między podanymi parami wierzchołków

Jaka jest złożoność następującego problemu?

Wejście :

• aścieżka hamiltonowskaw K n$H$$K_n$
• podzbiór par wierzchołków$R \subseteq [n]^2$
• dodatnia liczba całkowita $k$

Pytanie : czy istnieje pasujące , że dla każdego ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (gdzie G = ( [ n ] , M ∪ H ) )$M$$(v,u) \in R$$d_G(v,u) \leq k$
$G = ([n], M\cup H)$

Rozmawiałem z przyjacielem na ten temat. Mój przyjaciel uważa, że ​​problem dotyczy czasu wielomianowego. Myślę, że jest kompletny NP.

Ta odpowiedź jest niepoprawna .

Twój przyjaciel ma rację. Twój problem (jak interpretowane przez Sasho) nie nakłada żadnych ograniczeń na cardinality pasującym . W związku z tym, należy wybrać C się dopasowanie między parami R . Następnie dla każdej dodatniej liczby całkowitej k odległość między każdą parą w R jest mniejsza niż k .$C$$C$$R$$k$$R$$k$

Twój problem staje się interesujące, jeśli zmusić ścieżki zawierać krawędzie zarówno z pasującym a ścieżka P .$C$$P$

AKTUALIZACJA: odpowiedź poniżej jest nieprawidłowa, ponieważ błędnie założyłem, że ścieżka hamiltonowska jest na dowolnym wykresie, a nie w $K_n$ . Zostawiam to nieodkryte, być może uda mi się to naprawić lub da wskazówki dotyczące kolejnej odpowiedzi.

Myślę, że jest kompletny z NP. To bardzo nieformalna / szybka redukcja pomysłu 3SAT

Dla każdej zmiennej $x_i$ dodaj gadżet „Zmienna” z:

• trzy węzły $X_i, +X_i, -X_i$
• dwie zmienne krawędzie i ( X i , - X i$(X_i,+X_i)$$(X_i,-X_i)$

Dodaj węzeł źródłowy i podłącz go do wszystkich zmiennych X $S$$X_i$ .

Dla każdego punktu dodać węzeł C j i podłączyć do odpowiednich zmiennych + X i i - X I , który tworzy punkt.$C_j$$C_j$$+X_i$$-X_i$

Poniższy obraz przedstawia: $(+x_1 \lor -x_2 \lor -x_3) \land (-x_2 \lor x_3 \lor x_4)$

Zestaw (węzłów, które muszą być połączone) zawiera ( S , C 1 ) , ( S , C, 2 ) , . . $R$$(S, C_1), (S,C_2), ...$

Prosta ścieżka powinna obejmować wszystkie „NIEBIESKIE” krawędzie oprócz krawędzi zmiennych ( X i , + X i ) i ( X i , - X i ) (na zdjęciu powyżej niebieskie krawędzie reprezentują krawędzie, które uwzględniamy w $P$$(X_i, +X_i)$$(X_i, -X_i)$$P$ ).

W tym momencie, początkowy wzór jest spe tylko wtedy, gdy po najkrótszej drodze z z każdego punktu węzła C, j jest nie większa niż trzy. Rzeczywiście, aby osiągnąć zapis z S w trzech etapach trzeba przechodzić przez co najmniej jedną zmienną X i : S → X i → ± X i → C j . Musimy więc przejść przez jedną z dwóch krawędzi: X i → + X i lub X i → - X i ) i dołączyć ją do $S$$C_j$$S$$X_i$$S \to X_i \to \pm X_i \to C_j$$X_i \to +X_i$$X_i \to -X_i)$$C$(ponieważ z założenia nie jest to część ). Ale oba nie mogą być uwzględnione, ponieważ dzielą wierzchołek.$P$

Ale nie jesteśmy pewni, czy możemy zbudować prostą ścieżkę która obejmuje wszystkie niebieskie krawędzie, ponieważ niektóre węzły mają więcej niż jeden padający niebieski brzeg.$P$

Aby to naprawić, zastępujemy każdy węzeł wieloma incydentalnymi niebieskimi krawędziami, drzewem zawierającym tylko pary incydentalnych niebieskich krawędzi, które zostaną uwzględnione w i krawędzi, które je oddzielą i które powinny zostać uwzględnione w C, aby osiągnąć węzły klauzul:$P$$C$

Oryginalny wykres staje się:

$K$$C_j$$S$

$C$

$P$