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 $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 , ? (gdzie ) $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.

— pfim
źródło

Możesz to jeszcze bardziej uprościć, przynajmniej pod względem prezentacji. Otrzymujesz

, ścieżkę z

wierzchołkami i zbiór

par tych wierzchołków. Chcesz rozszerzyć ścieżkę o dopasowanie, aby odległość między dowolnymi parami w

wynosiła co najwyżej

k

$k$

n

$n$

R

$R$

R

$R$

k

$k$

— Sasho Nikolov

Myślę, że to sformułowanie może być mylące po mojej ostatniej edycji w celu usunięcia niejasności.

— pfim

Moja interpretacja jest poprawna, prawda?

— Sasho Nikolov

Zrobiłem edycję, aby bardziej precyzyjnie opisać problem. Myślę, że można to jeszcze bardziej uprościć, ponieważ można po prostu założyć, że H jest ścieżką hamiltonowską 1-2-3-4-5 ...- n bez utraty ogólności. Potrzebujesz tylko

n

$n$

— Kaveh

Odpowiedzi:

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ć się dopasowanie między parami . Następnie dla każdej dodatniej liczby całkowitej odległość między każdą parą w jest mniejsza niż . $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 . $C$ $P$

— Mohammad Al-Turkistany
źródło

Co rozumiesz przez „dopasowanie między parami w

”?

R

$R$

— Emil Jeřábek 3.0

@ EmilJeřábek Oznacza połączenie węzłów każdej pary w

za pomocą krawędzi. Więc

jest po prostu

z krawędzią łączącą każdą parę. Jest to równoważne zwiększając ścieżki

o doskonałej Idąc par

R

$R$

C

$C$

R

$R$

P

$P$

R

$R$

— Mohammad Al-Turkistany

Nie wydaje mi się to mieć większego sensu. Co jeśli

nie pasuje? Powiedzmy, jeśli

zawiera pary

, jak wybrać

R

$R$

R

$R$

(1, 2)

$(1,2)$

(1, 3)

$(1,3)$

C

$C$

— Emil Jeřábek 3.0

@ EmilJeřábek Tak. Twój punkt jest ważny. Zmienię swoją odpowiedź.

— Mohammad Al-Turkistany

@pfim Czy najkrótszą ścieżkę można utworzyć przy użyciu tylko krawędzi z

C

$C$

— Mohammad Al-Turkistany

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)$

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

Dla każdego punktu dodać węzeł i podłączyć do odpowiednich zmiennych 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 $R$ $(S, C_1), (S,C_2), ...$

Prosta ścieżka powinna obejmować wszystkie „NIEBIESKIE” krawędzie oprócz krawędzi zmiennych 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 jest nie większa niż trzy. Rzeczywiście, aby osiągnąć zapis z w trzech etapach trzeba przechodzić przez co najmniej jedną zmienną : . Musimy więc przejść przez jedną z dwóch krawędzi: lub 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 aby osiągnąć węzły klauzul: $P$ $C$

Oryginalny wykres staje się:

$K$ $C_j$ $S$

$C$

$P$

— Marzio De Biasi
źródło

Martwi mnie próba zbudowania ścieżki zawierającej wszystkie niebieskie krawędzie: niektóre wierzchołki mają na sobie więcej niż 2 niebieskie krawędzie, więc nie może istnieć żadna prosta ścieżka, w tym wszystkie niebieskie krawędzie.

— Michaił Rudoy,

Ok, dziękuję ... Całkowicie zapomniałem, co jest prostą ścieżką :-( ... teraz powinno być naprawione.

— Marzio De Biasi

Ten post na math.SE sugeruje, że problem może nie być NP-zupełny. Może to być trudne, ale możliwe do rozwiązania w quasipolynomialnym

— Mohammad Al-Turkistany

@ MohammadAl-Turkistany: czy widzisz wadę w obecnej wersji odpowiedzi?

— Marzio De Biasi,

Nie, nie widzę żadnej oczywistej wady.

— Mohammad Al-Turkistany,