Skierowane trudne NP problemy na DAG

12

Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Kilka problemów trudnych dla NP można rozwiązać na wykresach z ograniczoną szerokością drzewa. Jeśli na drzewach nadal występuje trudny NP, szerokość drzewa nie może nas uratować. Taka była motywacja jednego z moich wcześniejszych pytań, które dotyczyły trudnych NP problemów na drzewach.

Istnieje kilka ukierunkowanych wersji szerokości drzewa mierzących, jak blisko skierowany wykres jest do ukierunkowanego wykresu acyklicznego (DAG). Jakie są niektóre ukierunkowane problemy, które pozostają trudne dla NP w DAG? Ukierunkowany problem w istotny sposób wykorzystuje kierunki krawędzi. Na przykład ścieżka hamiltonowska jest ukierunkowanym problemem, podczas gdy pokrycie wierzchołków nie. Jedna z odpowiedzi na moje poprzednie pytanie zawierała ogólny przepis na generowanie problemów, które są trudne dla drzew. Czy istnieje taki przepis na DAG?

np-hardness directed-acyclic-graph

— Shiva Kintali
źródło

7

Ma to na celu jedynie częściową odpowiedź na pierwsze pytanie w poście:

Jakie są niektóre ukierunkowane problemy, które pozostają trudne dla NP w DAG?

W [1] podano kilka naturalnych problemów na ukierunkowanych wykresach, które pozostają NP-twarde na DAG. Motywacja artykułu polega na znalezieniu „dobrego” miernika poprzecznego dla wykrojników. Twierdzą, że wadą wielu miar dla digrafów jest to, że są one stałe dla DAG, ale wiele ukierunkowanych odpowiedników problemów naturalnych pozostaje NP-trudnych dla DAG. Aby uzyskać więcej informacji na ten temat, zobacz także [2] i odniesienia do tych artykułów.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: O pomiarach szerokości wykroju w sparametryzowanych algorytmach. IWPEC 2009: 185–197. Pełna wersja

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Czy są jakieś dobre miary szerokości wykroju? IPEC 2010, aby się pojawić. arXiv

— Serge Gaspers
źródło

6

Wiadomo, że kilka problemów z routingiem jest trudnych NP, a nawet trudnych do przybliżenia do czynników wielomianowych w DAG. Należą do nich takie problemy, jak maksymalne rozbieżne ścieżki i minimalizacja zatorów. Zobacz artykuły Andrews, Chuzhoy, Khanna, Zhang i innych, aby uzyskać więcej wskazówek.

— Chandra Chekuri
źródło

1

$\varphi:=\exists C_1 C_2 C_3 [\forall x (C_1 x \lor C_2 x \lor C_3 x) \land \bigwedge_{i=1,2,3}\forall x,y(\neg C_i x \lor \neg C_i y\lor \neg E(x,y))]$ $G$ $G'$ $E(x,y)$ $\varphi$ $E(x,y)\lor E(y,x)$ $G\models\varphi\iff G'\models\varphi'$

— Prawidłowość
źródło

Wydaje się, że problemem tym nie jest używanie kierunków krawędzi. Szukam ukierunkowanych problemów.

— Shiva Kintali,

@Shiva: Dlaczego to nie spełnia kryteriów ukierunkowanego problemu?

— András Salamon,

@ András: Kolorowanie wykresów dba o obecność krawędzi (u, v). Nie ma znaczenia, czy krawędź jest skierowana od u do v czy od v do u. Z drugiej strony Hamiltonian Path używa kierunków krawędzi. Można zmienić kierunki niektórych krawędzi i przekonwertować instancję TAK na instancję NIE.

— Shiva Kintali

@Shiva: Więc chcesz mieć właściwość wyrażoną formułą, która nie jest symetryczna (niezmienna przy permutacji zmiennych)?

— András Salamon,

@ András: Dokładnie.

— Shiva Kintali

1

Słynny problem OPEN [8] z listy Garey i Johnson wykracza poza P, ale można go udowodnić jako NP-C. Ten problem dotyczy DAG. W każdej rundzie można usunąć maksymalnie trzy wierzchołki, które nie mają krawędzi wejściowej. Zdecyduj, czy wszystkie wierzchołki DAG mogą zostać usunięte w K rundach? OTWARTY od 1970 roku.

— Peng Zhang
źródło