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?NPW[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?NPW[1]

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

cc.complexity-theory graph-algorithms parameterized-complexity fixed-parameter-tractable 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

Odpowiedzi:

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).k k G k = 2 G.GkkGk=2G

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