Jaka jest złożoność tego problemu ścieżki?

Instancja: Niekierowany wykres $G$ z dwoma wyróżniającymi się wierzchołkami i liczbą całkowitą .$s\neq t$$k\geq 2$

Pytanie: Czy istnieje ścieżka w , taka, że ​​ścieżka dotyka co najwyżej wierzchołków? (Ścieżka dotyka wierzchołka, jeśli wierzchołek znajduje się na ścieżce lub ma ścieżkę sąsiada).$s-t$$G$$k$

Problem ten zbadano w:

Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg: Utajone problemy z łącznością. ESA 2013: 301–312.

http://arxiv.org/pdf/1212.6176v1.pdf

Nazywali to problemem ustronnej ścieżki. Rzeczywiście jest to trudne dla NP, a wersja optymalizacyjna nie ma przybliżenia o stałym współczynniku.

Motywacja, którą zapewniają autorzy, to ustawienie, w którym informacje są przesyłane ścieżką, a tylko sąsiedzi i węzły na ścieżce mogą je zobaczyć. Celem jest zminimalizowanie ekspozycji.

Edycja: Proszę zobaczyć odpowiedź użytkownika 20655 poniżej, aby znaleźć odniesienie do artykułu już wykazującego twardość tego problemu. Zostawię swój oryginalny post na wypadek, gdyby ktoś chciał zobaczyć ten alternatywny dowód.

===============

Rozważmy przykład MIN-SAT, który jest trudnym problemem NP , składającym się ze zmiennych i klauzule C = { c 1 , c 2 , c 3 , ⋯ } . Zmniejszymy to do twojego problemu ze ścieżką.$X = \{x_1, x_2, \cdots\, x_n\}$$C = \{c_1, c_2, c_3, \cdots\}$

Musimy dwóch wierzchołków dla każdego (po jednej dla formy zanegowanym i jeden dla unnegated) i jeden dla każdego wierzchołka C i . Ponadto, pozwalając m = 2 n + | C | , będziemy mieli m wierzchołków p 1 , p 2 , ⋯ , p m do wypełnienia.$x_i$$c_i$$m = 2n+|C|$$m$$p_1, p_2, \cdots, p_{m}$

Ogólnie rzecz biorąc, będzie skonstruować krzywą gdzie rozwiązanie optymalne będzie budować ścieżkę z na T używając x i y i Ż x i y w węzłach pośrednich. Koszt tej drodze będzie dokładnie c j e, że ścieżka wybraliśmy zadowoli gdybyśmy przekształcić go zadania. W p I s są po prostu tam, aby zapobiec rozwiązanie optymalne z bycia w stanie oszukać przez krótkie cięcia przez którekolwiek z c j s.$s$$t$$x_i$$\bar{x_i}$$c_j$$p_i$$c_j$

Połącz klauzuli c j , w którym X i pojawia się i ¯ x I klauzuli c j , w którym ¯ x i pojawi. Aby wymusić zadanie zmiennych wykonujemy diament drabiny jak struktura, w którym X I i Ż X i są połączone ze sobą z x i + 1 i Ż x i + 1 . s jest podłączony zarówno do x 1, jak i $x_i$$c_j$$x_i$$\overline{x_i}$$c_j$$\overline{x_i}$$x_i$$\overline{x_i}$$x_{i+1}$$\overline{x_{i+1}}$$s$$x_1$ itsą połączone zarówno zxn, jaki ¯ x n . Na koniec, każdycijest połączona do wszystkich zmiennych wypełniającepj. Nie mam pod ręką mojego oprogramowania do rysowania wykresów, więc oto (wyjątkowo) narysowany schemat tej konstrukcji:$\overline{x_1}$$t$$x_n$$\overline{x_n}$$c_i$$p_j$

(Uwaga: chmura tutaj tylko duży zbiór wierzchołków, a grubość każdej z krawędzi c j do tej chmury oznacza C j są połączone ze sobą wierzchołkiem w zestawie).$\{P_i\}$$c_j$$c_j$

Twierdzenie jest takie, że w optymalnym rozwiązaniu problemu ścieżki dotykającej min, liczba wierzchołków, które dotkną ścieżki to , gdzie Q jest optymalnym rozwiązaniem instancji MIN-SAT. To dlatego, że$Q + 2n + 2$$Q$

1. Ścieżka musi zaczynać się od kończyć o t , a najlepszym sposobem na to bez zbierania wszystkich wierzchołków wypełnienia jest ciągłe przechodzenie od y i ∈ { x i , ¯ x i } do y i + 1 ∈ { x i + 1 , ¯ x i + 1 } bez zbierania zarówno x i jak i ¯ x i dla dowolnego i ∈ 1 , ⋯ , $s$$t$$y_i \in \{x_i, \overline{x_i}\}$$y_{i+1} \in \{x_{i+1}, \overline{x_{i+1}}\}$$x_i$$\overline{x_i}$$i \in 1, \cdots, n$(jest to intuicyjne, ponieważ usunięcie jednej z dwóch opcji z dowolnej wybranej dwukrotnie zmiennej daje prawidłową ścieżkę o koszcie nie większym niż koszt, który mieliśmy w sobie).
2. Istnieje rozwiązanie kosztu co najwyżej które idzie s , x 1 , x 2 , ⋯ , x n , t , zbierając nic poza s , t , { x i } , { ¯ x i } i { c i } . Ponieważ każda ścieżka s - t, która zawiera dowolne wypełnienie, musi zawierać co najmniej s , t , trochę $m+2$$s, x_1, x_2, \cdots, x_n, t$$s$$t$$\{x_i\}$$\{\overline{x_i}\}$$\{c_i\}$ $s-t$$s$$t$ , niektóre x i i x j , i wszystkie { p } , ma koszt ≥ m + 5 , więc jest nieoptymalny. Zatem optymalne rozwiązanie nie dotyka żadnego z wierzchołków dopełniania, więc ścieżka musi przebiegać zgodnie z opisem w części (1).$c_i$$x_i$$x_j$$\{p\}$$\geq m+5$
3. Wywołaj przypisania zmiennych odpowiadające wierzchołkom, przez które przechodzi ścieżka (innym niż i t ), wywołane przypisanie ścieżki. Wierzchołek C j styka IFF indukowanego przypisania ścieżki odpowiadałoby klauzuli c j . Odwrotnie, przypisania zmienne, które spełnia Q klauzule może być przekształcona w ścieżce, która dotyka dokładnie P o c J s patrząc na ścieżkę, która powoduje że zadania.$s$$t$$c_j$$c_j$$Q$$Q$$c_j$
4. Każdy i Ż x i dotyka tej ścieżki, jak również obie s i t . Łącznie stanowią one 2 n + 2 w całkowitym koszcie. Reszta pochodzi z dotkniętych c i kosztem Q w optymalnym rozwiązaniu.$x_i$$\overline{x_i}$$s$$t$$2n + 2$$c_i$$Q$

Możemy więc sprawdzić, czy instancja MIN-SAT ma rozwiązanie kosztu jeśli tworzony przez nas wykres ma koszt ≤ k + 2 n + 2 w przypadku problemu z twoją ścieżką. W szczególności możemy to zrobić poprzez zmniejszenie Karp. Tak więc, jak stwierdzono, trudny jest NP.$\leq k$$\leq k + 2n + 2$