Problemy z grafem, które są NP-Complete na grafach ukierunkowanych, ale wielomianowe na grafach niekierowanych

Szukam problemów, które są znane jako NPC dla grafów kierowanych, ale mają algorytm wielomianowy dla grafów bezkierunkowych.

Widziałem pytanie dotyczące odwrotnych problemów, które są łatwiejsze niż ich „niekierowany” wariant , ale szukam twardości po stronie ukierunkowanej.

Na przykład, zestaw krawędzi sprzężenia zwrotnego jest znany jako NPC na ukierunkowanych, ale wielomianowych rozwiązanych na niekierowanych grafach.

Jakie inne naturalne problemy mają tę samą właściwość?

Pierwszy problem, jaki przychodzi mi do głowy, to problem z 2 ścieżkami (lub bardziej ogólnie problem z ścieżką K). Biorąc pod uwagę i ( s 2 , t 2 ) , znajdź dwie rozłączne ścieżki odpowiednio od s 1 do t 1 i s 2 do t 2 . Problemem jest NPC dla grafów ukierunkowanych, ale rozwiązany w czasie wielomianowym dla grafów bezkierunkowych (choć nie jest to banalny).$(s_1,t_1)$$(s_2,t_2)$$s_1$$t_1$$s_2$$t_2$

$NP$

W problemie kolorowania ścieżek otrzymujemy drzewo T i zbiór ścieżek na tym drzewie (chodzi o to, że T jest siecią komunikacyjną, a ścieżki są żądaniami komunikacji). Chcemy pokolorować ścieżki minimalną liczbą kolorów, aby dwie ścieżki, które mają wspólną krawędź, miały różne kolory.

Wiadomo, że ten problem można rozwiązać w czasie wielomianowym, jeśli T jest drzewem o nieukierowanym stopniu. Jest jednak NP-kompletny, jeśli T jest dwukierunkowym drzewem binarnym. Uważam, że oba wyniki podano w poniższej pracy.

[1] T. Erlebach i K. Jansen. „Złożoność kolorowania ścieżek i planowania połączeń”. Theoretical Computer Science, 255 (1-2): 33–50, 2001.

Jeśli się nie mylę, uzyskanie stałego przybliżenia współczynnika dla drzewa Steiner'a jest trudne dla NP na grafach skierowanych, ale jest czasem P dla grafów bezkierunkowych.