Co odróżnia łatwe globalne problemy od twardych globalnych problemów na wykresach ograniczonej szerokości?

Wiele trudnych problemów graficznych można rozwiązać w czasie wielomianowym na wykresach ograniczonej szerokości . Rzeczywiście, podręczniki zwykle używają np. Zestawu niezależnego jako przykładu, co jest problemem lokalnym . Z grubsza problem lokalny to problem, którego rozwiązanie można zweryfikować, badając niewielkie sąsiedztwo każdego wierzchołka.

Co ciekawe, nawet problemy (takie jak ścieżka Hamiltona) o charakterze globalnym nadal można skutecznie rozwiązać dla ograniczonych wykresów szerokości. W przypadku takich problemów zwykłe algorytmy programowania dynamicznego muszą śledzić wszystkie sposoby, w jakie rozwiązanie może przejść przez odpowiedni separator rozkładu drzewa (patrz np. [1]). Algorytmy randomizowane (oparte na tzw. Cut'n'count) podano w [1], a ulepszone (nawet deterministyczne) algorytmy opracowano w [2].

Nie wiem, czy można powiedzieć tyle, ale przynajmniej niektóre globalne problemy można skutecznie rozwiązać dla wykresów ograniczonej szerokości. A co z problemami, które pozostają trudne na takich wykresach? Zakładam, że mają one również charakter globalny, ale co jeszcze? Co odróżnia te trudne globalne problemy od globalnych problemów, które można skutecznie rozwiązać? Na przykład, w jaki sposób i dlaczego znane metody nie zapewniłyby nam wydajnych algorytmów?

Na przykład można rozważyć następujące problemy:

Krawędź precoloring przedłużenie Biorąc pod uwagę wykres z jakimiś kolorowymi krawędziami, zdecydować, czy kolorystyka może zostać przedłużony do właściwego -edge-kolorowania grafu .$G$$k$$G$

Rozszerzenie wstępnego kolorowania krawędzi (i jego wariant kolorowania krawędzi listy) jest NP-kompletny dla dwustronnych wykresów szeregowo-równoległych [3] (takie wykresy mają szerokość co najwyżej 2).

Minimalna suma kolorowania krawędzi Biorąc pod uwagę wykres , znajdź kolorowanie krawędzi tak że jeśli i mają wspólny wierzchołek, to . Celem jest zminimalizowanie , sumy zabarwienia.$G=(V,E)$$\chi : E \to \mathbb{N}$$e_1$$e_2$$\chi(e_1) \neq \chi(e_2)$$E'_\chi(E) = \sum_{e \in E} \chi(e)$

Innymi słowy, musimy przypisać dodatnie liczby całkowite do krawędzi wykresu, tak aby sąsiednie krawędzie otrzymały różne liczby całkowite, a suma przypisanych liczb jest minimalna. Problem ten jest trudny dla NP dla częściowych drzew 2 [4] (tj. Wykresów szerokości grzbietu co najwyżej 2).

Inne takie trudne problemy obejmują problem ścieżek rozłącznych krawędzi, problem izomorfizmu podgrupy oraz problem z przepustowością (patrz np. [5] i odnośniki tam zawarte). W przypadku problemów, które pozostają trudne nawet na drzewach, zobacz to pytanie .

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, JM, i Wojtaszczyk, JO (2011, październik). Rozwiązywanie problemów z łącznością sparametryzowanych przez szerokość w jednym wykładniczym czasie. W Foundations of Computer Science (FOCS), 52. doroczne sympozjum IEEE 2011 (s. 150–159). IEEE.

[2] Bodlaender, HL, Cygan, M., Kratsch, S., i Nederlof, J. (2013). Deterministyczne algorytmy pojedynczego wykładniczego czasu dla problemów z łącznością sparametryzowanych przez szerokość. W automatach, językach i programowaniu (s. 196–207). Springer Berlin Heidelberg.

[3] Marks, D. (2005). NP - kompletność rozszerzenia listy i wstępnego kolorowania na krawędziach płaskich wykresów. Journal of Graph Theory, 49 (4), 313–324.

[4] Marks, D. (2009). Wyniki złożoności dla minimalnej sumy kolorowania krawędzi. Discrete Applied Mathematics, 157 (5), 1034-1045.

[5] Nishizeki, T., Vygen, J., i Zhou, X. (2001). Problem ścieżek rozłącznych krawędzi jest NP-kompletny dla wykresów szeregowo-równoległych. Discrete Applied Mathematics, 115 (1), 177-186.

Większość algorytmów dla wykresów ograniczonej szerokości opiera się na pewnej formie programowania dynamicznego. Aby te algorytmy były wydajne, musimy ograniczyć liczbę stanów w tabeli programowania dynamicznego: jeśli chcesz algorytm wielomianowy, to potrzebujesz wielomianową liczbę stanów (np. N ^ tw), jeśli chcesz pokaż, że problemem jest FPT, zwykle chcesz pokazać, że liczba stanów jest jakąś funkcją szerokości grzbietu. Liczba stanów zazwyczaj odpowiada liczbie różnych typów rozwiązań częściowych podczas łamania wykresu w pewnym małym separatorze. Tak więc problem jest prosty na wykresach o ograniczonej szerokości, zwykle dlatego, że częściowe rozwiązania oddziałujące ze światem zewnętrznym za pośrednictwem ograniczonej liczby wierzchołków mają tylko ograniczoną liczbę typów. Na przykład, w problemie zbioru niezależnego rodzaj rozwiązania częściowego zależy tylko od tego, które wierzchołki graniczne są wybrane. W problemie cyklu Hamiltonowskiego typ rozwiązania częściowego jest opisany przez to, jak podścieżki rozwiązania częściowego pasują do siebie wierzchołkami granicy. Warianty twierdzenia Courcelle'a dają wystarczające warunki, aby problem miał właściwość polegającą na tym, że częściowe rozwiązania mają ograniczoną liczbę typów.

Jeśli problem jest trudny na wykresach o ograniczonej szerokości, zwykle dzieje się tak z jednego z następujących trzech powodów.

1. Występują interakcje w problemie, które nie zostały wychwycone przez wykres. Na przykład Steiner Forest jest trudny do NP na wykresach szerokości 3, intuicyjnie, ponieważ pary źródło-miejsce docelowe tworzą interakcje między nieprzylegającymi wierzchołkami.

Elisabeth Gassner: Powrót do problemu lasu Steinera. J. Discrete Al Algorytmy 8 (2): 154-163 (2010)

MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marks: Schematy aproksymacyjne dla Steiner Forest na płaskich wykresach i wykresach ograniczonej poprzeczności. J. ACM 58 (5): 21 (2011)

2. Problem jest zdefiniowany na krawędziach wykresu. Wtedy nawet jeśli część wykresu jest dołączona do reszty wykresu za pomocą ograniczonej liczby wierzchołków, może wystąpić wiele krawędzi padających na te kilka wierzchołków, a następnie stan częściowego rozwiązania można opisać tylko przez opisanie stanu wszystkie te krawędzie. To sprawiło, że problemy w [3,4] były trudne.

3. Każdy wierzchołek może mieć wiele różnych stanów. Na przykład, Capacitated Vertex Cover ma twardość W [1] sparametryzowaną przez szerokość, intuicyjnie, ponieważ opis rozwiązania częściowego obejmuje nie tylko określenie, które wierzchołki separatora zostały wybrane, ale także stwierdzenie, ile razy każdy wybrany wierzchołek separatora był służy do zakrywania krawędzi.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Capacitated Domination and Covering: A Parameterized Perspective. IWPEC 2008: 78–90

Moją sugestią byłoby przyjrzenie się uważnie twierdzeniu Courcelle'a , że problemy wyrażalne w (pewnych rozszerzeniach) monadycznej logiki drugiego rzędu mają algorytmy FPT, gdy są sparametryzowane przez szerokość. Podejrzewam, że obejmuje to wiele lub większość znanych przykładów problemów FPT dla tych wykresów. W tym widoku twoje lokalne / globalne rozróżnienie wydaje się być blisko związane z rozróżnieniem między problemami wyrażanymi w egzystencjalnym MSO a problemami, które mają wyższy poziom kwantyfikacji w swoich formułach MSO. Wracając do twojego aktualnego pytania, brak sformułowania MSO (który można udowodnić bezwarunkowo w wielu przypadkach przy użyciu pomysłów związanych z twierdzeniem Myhill – Nerode ) byłby dowodem na brak algorytmu FPT (trudniej udowodnić bez założeń teoretycznych).

Myślę, że jednym z takich przykładów jest najrzadszy problem cięcia. Jednolity problem cięcia rzadkiego jest rozwiązywalny na wykresach ograniczonej szerokości drzewa, ale ważony problem cięcia rzadkiego nie jest nawet w przybliżeniu (lepszy niż 17/16) na wykresach ograniczonej szerokości drzewa.

Istnieje wiele różnych wariantów najrzadszego problemu cięcia, ale jeden z dobrze znanych jest następujący.

$G=(V,E)$$w:E(G)\rightarrow N$$E(S,V\setminus S) \subseteq E(G)$$S \subset V$$\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$$E'\subseteq E(G)$$W(E')=\sum_{e\in E'}w(e)$

Główny składnik składa się z dwóch rzeczy:

1. Dodatkowe funkcje, jak tutaj funkcja wagi. Ale nadal istnieją pewne problemy z funkcją wagi, które nie są bardzo trudne w niekierowanych grafach szerokości ograniczonego drzewa.

2. Charakter najrzadszego problemu cięcia. W rzeczywistości istnienie więcej niż jednej zależności dla programowania dynamicznego w definicji problemu. Intuicyjnie dobrym rozwiązaniem jest to, że dzielimy wykres (usuwając niektóre krawędzie) na dwa prawie równe rozmiary, z drugiej strony w tej partycji usuwamy najmniejszą liczbę używanych krawędzi. Przyczyną tego, że problem jest trudny na ograniczonym wykresie szerokości, jest to, że powinniśmy zastosować programowanie dynamiczne w dwóch kierunkach, ale oba kierunki są od siebie zależne.

Ogólnie rzecz biorąc, jeśli problem jest taki, że do programowania dynamicznego potrzeba więcej niż jednego wymiaru, a także te wymiary są od siebie zależne, wówczas problem może być trudny na wykresach o ograniczonej szerokości drzewa. Widzimy ten wzór zarówno w problemach w pytaniu, jak i w przypadku problemu najrzadszego cięcia. (W pierwszym problemie chcemy zachować poprzednie kolorowanie, z drugiej strony utrzymywać kolor tak mały, jak to możliwe, w drugim problemie oczywiście są dwie funkcje, które są od siebie zależne)