Skierowane trudne NP problemy na DAG

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?

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

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.

$\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'$

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.