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$

cc.complexity-theory graph-theory graph-algorithms

— Andras Farago
źródło

To brzmi jak ograniczona minimalizacja podmodularna. Niestety nie jest jasne, czy zestaw ograniczeń dopuszcza skuteczne rozwiązanie.

— Suresh Venkat

Moja odpowiedź

był prawdopodobnie błędne! Po dokładniejszym sprawdzeniu heurystyka nie wydaje się monotonna.

A^{*}

$A^*$

— usul

Kontynuując komentarz Suresha, warto zapoznać się z artykułem „Przybliżalność problemów kombinatorycznych z wielomagodowymi funkcjami kosztów submodularnych”, który pokazuje, że najkrótsza ścieżka kosztów submodularnych jest trudna. Może istnieją pomysły, które pokazują twardość. computer.org/csdl/proceedings/focs/2009/3850/00/…

— Chandra Chekuri

Problem ten można przeformułować jako znalezienie pod-grafu gąsienicy z co najwyżej

wierzchołkami, który zawiera

na jego najdłuższej ścieżce.

k

$k$

s

$s$

t

$t$

— Obinna Okechukwu

@Obinna pod-wykres gąsienicy musi być w pewnym sensie maksymalny, ponieważ musimy uwzględnić wszystkich sąsiadów najdłuższej ścieżki

— SamM

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.

— użytkownik20655
źródło

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 . 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 . Ponadto, pozwalając , będziemy mieli wierzchołków 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 używając y i y w węzłach pośrednich. Koszt tej drodze będzie dokładnie e, że ścieżka wybraliśmy zadowoli gdybyśmy przekształcić go zadania. W s są po prostu tam, aby zapobiec rozwiązanie optymalne z bycia w stanie oszukać przez krótkie cięcia przez którekolwiek z s. $s$ $t$ $x_i$ $\bar{x_i}$ $c_j$ $p_i$ $c_j$

Połącz klauzuli , w którym pojawia się i klauzuli , w którym pojawi. Aby wymusić zadanie zmiennych wykonujemy diament drabiny jak struktura, w którym i są połączone ze sobą z i . jest podłączony zarówno do 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$ isą połączone zarówno zi . Na koniec, każdyjest połączona do wszystkich zmiennych wypełniające. 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$

Konstrukcja twardego instancji

(Uwaga: chmura tutaj tylko duży zbiór wierzchołków, a grubość każdej z krawędzi do tej chmury oznacza 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 jest optymalnym rozwiązaniem instancji MIN-SAT. To dlatego, że $Q + 2n + 2$ $Q$

Ścieżka musi zaczynać się od kończyć o , a najlepszym sposobem na to bez zbierania wszystkich wierzchołków wypełnienia jest ciągłe przechodzenie od do bez zbierania zarówno i dla dowolnego $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).
Istnieje rozwiązanie kosztu co najwyżej które idzie , zbierając nic poza , , , i . Ponieważ każda ścieżka która zawiera dowolne wypełnienie, musi zawierać co najmniej , , 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 i , i wszystkie , ma koszt , 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$
Wywołaj przypisania zmiennych odpowiadające wierzchołkom, przez które przechodzi ścieżka (innym niż i ), wywołane przypisanie ścieżki. Wierzchołek styka IFF indukowanego przypisania ścieżki odpowiadałoby klauzuli . Odwrotnie, przypisania zmienne, które spełnia klauzule może być przekształcona w ścieżce, która dotyka dokładnie o s patrząc na ścieżkę, która powoduje że zadania. $s$ $t$ $c_j$ $c_j$ $Q$ $Q$ $c_j$
Każdy i dotyka tej ścieżki, jak również obie i . Łącznie stanowią one w całkowitym koszcie. Reszta pochodzi z dotkniętych kosztem 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 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$

— Yonatan N.
źródło