Prosta ścieżka na sztyfcie z tylnymi krawędziami

Jaka jest złożoność następującego problemu ( P? NP-trudny?): $\in$

Dane wejściowe: ukierunkowany wykres acykliczny , zestaw tylnych krawędzi i dwa odrębne węzły $D=(V,E)$ $E'\subset V\times V$ $s$ i . $t$

Pytanie: Niech oznacza wykres utworzony przez dodanie do krawędzi od . Czy istnieje prosta ścieżka od do w która wykorzystuje co najmniej jedną krawędź wsteczną? $G=(V,E\cup E')$ $D$ $E'$ $s$ $t$ $G$

Uwaga: 0) Prosta ścieżka to ścieżka, w której żaden wierzchołek się nie powtarza. Krawędź wsteczna to krawędź, która jest sprzeczna z częściową kolejnością sugerowaną przez DAG. 1) problem jest prosty, jeśli poprosimy prostą ścieżkę o użycie dokładnie jednej krawędzi wstecznej (lub liczby stałej) poprzez trywialną redukcję do problemu ścieżki rozłącznej, która dopuszcza proste rozwiązanie PTime w DAG ( Perl i Shiloach, JACM'78 ) 2) problem z rozłączną ścieżką jest NP-zupełny na ogólnych wykresach ( Fortune i in., TCS'80 ).

graph-algorithms time-complexity disjoint-paths

— Joseph Stack
źródło

To z pewnością nie jest optymalna, ale to wystarczy, aby pokazać, że problem jest w P (chyba że źle coś): Niech

będą krawędziami

; zastosowanie algorytmu najkrótszej ścieżki od

w wykres

dla

e_{1}, . . ., e_{m}

$e_1,...,e_m$

E

$E$

s

$s$

t

$t$

G_{i} = (V, E^{'} \cup ⋃_{j = 1}^{i} {e_{j}})

$G_i = (V, E' \cup \bigcup_{j=1}^i \{ e_j \} )$

. Innymi słowy, dodawaj krawędź wybraną z

do wykresu

aż znajdziesz ścieżkę od

i = 1, 2, . . ., m

$i = 1,2,...,m$

E

$E$

G^{'} = (V, E^{'})

$G' = (V, E')$

s

$s$

t

$t$

— Marzio De Biasi

Marzio: ale co jeśli ścieżka, którą znajdziesz, używa tylko krawędzi w

i żadnej w

? Nadal może istnieć inna ścieżka, która obejmuje również krawędź

E

$E$

E^{'}

$E'$

E^{'}

$E'$

— David Eppstein,

To, co jest bardzo denerwujące w twoim problemie, to fakt, że następujący pokrewny problem jest łatwo zauważalny jako trudny do NP: biorąc pod uwagę wykres i dwie pary wierzchołków (s, t), (s ', t'), aby ustalić, czy występują rozłączenia wierzchołków ścieżki od s do t oraz od s 'do t', nawet gdy t = s ', a nawet na wykresach, które są sumą dwóch DAG. Mimo to nie wydaje się to pomocne w przypadku pytania, które zadajesz.

— a3nm

Problemem rozłącznych ścieżek jest W [1] - twardy nawet w DAG, i jest to zadanie domowe pokazujące, że w DAG jest trudne do NP. Algorytm Shiloach dotyczy problemu dwóch rozłącznych ścieżek i w nieco podobny sposób działa dla problemu k rozłącznych ścieżek w DAG, ale zajmuje to czas n ^ k. Ale przynajmniej przyznaje algorytm XP dla twojego problemu.

— Saeed,