Które problemy z grafem są trudne dla na wykresach skierowanych (/ ważonych), ale FPT na wykresach niekierowanych (/ nieważonych)?

10

Po równoważnych pytaniach dotyczących kompletności NP (patrz pytanie wagi i pytanie kierowane ) zastanawiałem się, w jaki sposób atrybuty te wpływają na sparametryzowane problemy.

Które problemy z twardym grafem są trudne dla na grafach ukierunkowanych, ale stały parametr można traktować na grafach bezkierunkowych? $NP$ $W[1]$

Które problemy z twardym grafem są trudne dla na wykresach ważonych, ale stały parametr można traktować na wykresach nieważonych? $NP$ $W[1]$

OK, więc mamy problemy, które stają się trudniejsze w wersji kierowanej. Co z ciężarami? Czy mogą utrudnić sparametryzowany problem?

— RB
źródło

Istnieją przypadki, które nie są dokładnie takie same i nie są znane. np. obliczanie szerokości drzewa na niekierowanych grafach jest fpt, ale obliczanie szerokości drzewa ukierunkowanego nie jest znane, jeśli jest fpt. ale w etalowym dziele Johnsona istnieje przybliżenie 3 fpt.

— Saeed,

2

Lub inny przypadek, gdy gramy w grę szerokości DAG na niekierowanych grafach, uzyskujemy rozkład drzewa. Ale szerokość drzewa obliczeniowego to FPT, ale szerokość obliczeniowego sztyletu jest kompletna z PSPACE .

— Saeed

9

Problem ścieżek rozłącznych: przy danych parach i węzłów istnieją ścieżki rozłączne węzłów łączące podane pary. Sparametryzowane przez , w FPT, gdy ma bezpośredniego związku z przełomowym dziełem Robertsona i Seymour. NP-Hard dla gdy jest skierowany - z pracy Fortune, Hopcroft i Wylie (1980). $G$ $k$ $k$ $G$ $k=2$ $G$

— Chandra Chekuri
źródło

3

Obliczanie szerokości drzewa i rozkładu drzewa na niekierowanych grafach jest parametrem FPT wrt width. Wiele miar szerokości wykroju (lub odpowiadającej im gry) jest równoważnych szerokości drzewa na niekierowanych wykresach. Dokładna klasa złożoności wielu z nich nie jest znana, ale ostatnio wykazano, że szerokość DAG jest kompletna z PSPACE .

— Saeed
źródło