Algorytmiczne zalety szerokości ścieżki w porównaniu do szerokości

Treewidth odgrywa ważną rolę w algorytmach FPT, częściowo dlatego, że wiele problemów jest FPT parametryzowanych przez treewidth. Powiązanym, bardziej ograniczonym pojęciem jest szerokość ścieżki. Jeśli wykres ma szerokość ścieżki , ma również szerokość co najwyżej , podczas gdy w kierunku przeciwnym, szerokość oznacza tylko szerokość ścieżki co najwyżej a to jest ciasne. $k$ $k$ $k$ $k\log n$

Biorąc pod uwagę powyższe, można oczekiwać, że wykresy ograniczonej ścieżki mogą mieć znaczącą przewagę algorytmiczną. Wydaje się jednak, że większość problemów FPT dla jednego parametru to FPT dla drugiego. Jestem ciekawy, czy istnieją jakieś przeciwne przykłady, to znaczy problemy, które są „łatwe” dla ścieżki, ale „trudne” dla szerokości.

Pozwól mi wspomnieć, że byłem zmotywowany, aby zadać to pytanie, natrafiając na najnowszy artykuł Igora Razgona („O OBDD dla CNF o ograniczonej szerokości poprzecznej”, KR'14), który podał przykład problemu z rozwiązaniem , gdy jest pathwidth i a (w przybliżeniu) dolnej granicy, gdy jest treewidth. Zastanawiam się, czy istnieją inne okazy tego zachowania. $2^{k}n$ $k$ $n^k$ $k$

Podsumowanie: Czy są jakieś przykłady naturalnych problemów, które są W-twarde sparametryzowane przez szerokość, ale FPT sparametryzowane przez szerokość? Mówiąc szerzej, czy istnieją przykłady problemów, których złożoność jest znana / uważa się za znacznie lepszą, gdy jest parametryzowana przez szerokość ścieżki zamiast szerokości boku?

parameterized-complexity treewidth graph-minor

— Michael Lampis
źródło

Istnieją problemy, które są łatwe na ścieżkach, ale NP-Hard na drzewach. Obejmują one minimalną liczbę multutut i maksymalną liczbę pełnoprzepływową.

— Chandra Chekuri

@ChandraChekuri To dobra uwaga, ale czy algorytmy dla ścieżek dla takich problemów zwykle uogólniają się na szerokość ścieżki? Na przykład, dla maksymalnej liczby całkowitej multiflow, myślę, że tak nie jest. Garg, Vazirani i Yannakakis udowodnili twardość NP dla drzew w „Pierwotnych podwójnych algorytmach aproksymacyjnych dla całkowego przepływu i multututów w drzewach”. Redukcja tam wykorzystuje drzewo o wysokości 3. Oznacza to, że problem jest trudny do uzyskania w przypadku stałej szerokości ścieżki.

— Michael Lampis

To znowu nie jest czysta odpowiedź na pierwotne pytanie. Luka ograniczenia przepływu na wykresach k szerokości ścieżki jest znana z tego, że jest ograniczona przez f (k) dla niektórych funkcji f poprzez wynik Lee i Sidiropoulosa. Ważnym otwartym problemem jest to, czy taki wynik ma znaczenie dla szerokości. Przypadek k = 3 jest otwarty na szerokość.

— Chandra Chekuri

Najlepszy algorytm dla cyklu Hamiltoniana sparametryzowanego przez szerokość ścieżki ma czas działania

(arxiv.org/abs/1211.1506), podczas gdy najlepsza szerokość wynosi

(arxiv.org/abs/1103.0534) Jest to jednak prawdopodobnie tylko przerwa czekająca na zamknięcie.

(2 + \sqrt{2})^{p w}

$(2+\sqrt{2})^{pw}$

4^{t w}

$4^{tw}$

— daniello

Pokazano, że [1] problem mieszanego chińskiego listonosza (MCPP) sparametryzowany przez szerokość ścieżki ma twardość , nawet jeśli wszystkie krawędzie i łuki wykresu wejściowego mają wagę i są FPT w odniesieniu do treedepth. Jest to pierwszy problem, o którym wiadomo, że wykazano, że jest on twardy w odniesieniu do szerokości, ale FPT w odniesieniu do szerokości. Zauważ, że szerokość ścieżki na wykresie leży między jej szerokością a głębokością. $W[1]$ $G$ $1$ $W[1]$

Problem Steiner Multicut, co zmierza punktację nieukierunkowane wykres , zbiór , , zestawów końcowych wielkości co najwyżej i liczb całkowitych , czy znajduje się zestaw o co najwyżej krawędzi lub węzłów tak, że z każdego zestawu co najmniej jeden parę zacisków przyłączonych w różnych składników . $G$ $T = \{T_1, . . . , T_t\}$ $T_i ⊆ V(G)$ $p$ $k$ $S$ $k$ $T_i$ $G \ S$

Węzeł Steiner Multicut, Edge Steiner Multicut i Restr. Węzeł Steiner Multicut są -hard dla parametru , nawet jeśli , a [2]. $W[1]$ $k$ $p = 3$ $tw(G) = 2$

[1] https://core.ac.uk/download/pdf/77298274.pdf

[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf

— Rupei Xu
źródło