Sparametryzowana złożoność od P do NP-twardego iz powrotem

Szukam przykładów problemów sparametryzowanych liczbą , gdzie twardość problemu nie jest monotoniczna w k . Z mojego doświadczenia wynika, że większość problemów ma przejście jednofazowe, na przykład k- SAT ma przejście jednofazowe od k ∈ { 1 , 2 } (gdzie problem występuje w P) do k ≥ 3 (gdzie problemem jest NP- kompletny). Interesują mnie problemy, w których występują przejścia fazowe w obu kierunkach (od łatwego do trudnego i odwrotnie) wraz ze wzrostem k .$k \in \mathbb{N}$$k$$k$$k \in \{1,2\}$$k \ge 3$$k$

Moje pytanie jest nieco podobne do pytania zadanego podczas Skoków Twardości w Złożoności Obliczeniowej , a niektóre odpowiedzi w nim zawarte odnoszą się do mojego pytania.

Przykłady, o których wiem:

1. $k$ -kolorowalność płaskich wykresów: w P, z wyjątkiem gdy$k=3$ , gdzie jest NP-kompletna.
2. Drzewo Steinera z zaciskami $k$ : W P, gdy $k=2$ (zwalnia się do najkrótszej ścieżki $s$ - $t$ ), a gdy $k=n$ (zapada się do MST), ale NP-twarde „pomiędzy”. Nie wiem, czy te przejścia fazowe są ostre (np. P dla $k_0$ ale NP-twardy dla $k_0+1$ ). Również przejścia $k$ zależą od wielkości instancji wejściowej, w przeciwieństwie do moich innych przykładów.
3. Zliczanie zadowalające Przyporządkowanie płaską wzorze modulo W P, gdy n jest Mersenne pierwsza liczba n = 2 k - 1 i # P kompletne do (?) Większość / wszystkie inne wartości N (Aaron Sterling, w tym nici ) . Wiele przejść fazowych!$n$$n$$n=2^k-1$$n$
4. Wykrywanie wykrytego subgrafu: Problem nie jest parametryzowany przez liczbę całkowitą, ale przez wykres. Istnieją wykresy (gdzie ⊆ oznacza pewien rodzaj relacji podgraficznej), dla których ustalenie, czy H i ⊆ G dla danego wykresu G jest w P dla i ∈ { 1 , 3 }, ale NP- uzupełnij dla i = 2 . (od Hsien-Chih Chang w tym samym wątku ).$H_1 \subseteq H_2 \subseteq H_3$$\subseteq$$H_i \subseteq G$$G$$i\in \{1,3\}$$i=2$

Jednym z obszarów o dużej nie-monotoniczności złożoności problemów są testy właściwości. Niech jest zbiorem wszystkich n wykresów -Vertex i wywołać P ⊆ G n właściwość wykresu. Ogólnym problemem jest ustalenie, czy wykres G ma właściwość P (tj. G ∈ P ), czy też jest „daleki” od posiadania własności P w pewnym sensie. W zależności od tego, co to jest P i jaki dostęp do zapytania masz na wykresie, problem może być dość trudny.$\mathcal{G}_n$$n$$P \subseteq \mathcal{G}_n$$G$$P$$G \in P$$P$$P$

Łatwo jednak zauważyć, że problem nie jest monotoniczny, ponieważ jeśli mamy , fakt, że P jest łatwo testowalny, nie oznacza, że S jest łatwo testowalny lub że T jest. $S \subset P \subset T$$P$$S$$T$

Aby to zobaczyć, wystarczy zauważyć, że i p = ∅ oba trywialny testować, jednak dla niektórych właściwości, istnieje silne dolnych granic.$P = \mathcal{G}_n$$P = \emptyset$

Dla danego wykresu i liczby całkowitej k ≥ 1 , k-ta potęga G , oznaczona przez G k , ma taki sam zestaw wierzchołków, że dwa różne wierzchołki sąsiadują w G k, jeśli ich odległość w G wynosi co najwyżej k . Na k -tego moc podziału wykresu problemu pyta, czy dany graf jest w k -tym moc dzielonej wykresie.$G$$k\ge 1$$k$$G$$G^k$$G^k$$G$$k$$k$$k$

• Dla problem można rozwiązać w czasie liniowym. Jest tak, ponieważ rozpoznawanie podzielonych wykresów jest wykonalne w czasie liniowym (dobrze znane).$k=1$
• Dla problem jest NP-zupełny. Potwierdzają to Lau i Corneil w Rozpoznawaniu mocy odpowiedniego przedziału, podziału i wykresu akordowego , SIAM J. Discrete Math., 18 (2004), 83-102 .$k=2$
• Dla problem jest trywialny: tylko pełne wykresy są k- tymi potęgami podzielonego wykresu.$k\ge 3$$k$

Jednym z takich problemów jest kolorowanie krawędzi grafów płaskich, gdzie parametrem jest - maksymalny stopień wykresu. Gdy Δ = 2 lub Δ ⩾ 7, znane są algorytmy wielomianowe dokładne ( patrz tutaj ), podczas gdy dla takie algorytmy nie są znane i nie ma dowodów na twardość NP dla tych przypadków.$\Delta$$\Delta=2$$\Delta\geqslant 7$$3\leqslant\Delta\leqslant 6$

Powiązane pytanie omówiono tutaj .

Określanie, czy wykres ma dominującą klikę dla:$G$

• $diam(G)=1$ jest banalny - odpowiedź brzmi zawsze „tak”
• $diam(G)=2$ oznacza NP-zupełność
• $diam(G)=3$ oznacza NP-zupełność
• $diam(G)\ge 4$ jest banalny - odpowiedź brzmi zawsze „nie”

Przypadek wynika z Brandstädta i Kratscha , a przypadek jest odnotowany w moim ostatnim artykule .d i a m ( G ) = $diam(G)=3$$diam(G)=2$

Czy to jest przykład zjawiska, którego szukasz?

Zastanów się nad problemem k-kliki, gdzie k jest rozmiarem kliki, której szukamy. Problemem jest więc: „Czy na wykresie G na n wierzchołkach jest klika rozmiaru k?”

Dla wszystkich stałych k problem występuje w P. (Algorytm siły brutalnej działa w czasie .) Dla dużych wartości k, na przykład wartości takich jak n / 2, jest ona NP-zupełna. Kiedy k zbliża się bardzo do n, jak nc dla jakiegoś stałego c, problem pojawia się ponownie w P, ponieważ możemy przeszukać wszystkie podzbiory n wierzchołków o rozmiarze nc i sprawdzić, czy którykolwiek z nich tworzy klikę. (Istnieją tylko takie podzbiory , które są wielomianowo duże, gdy c jest stałą.)O ( n c$O(n^k)$$O(n^c)$

Oto przykład, którego możesz szukać. Ten parametr nie jest liczbą całkowitą, to para liczb. (Chociaż jeden z nich można naprawić, aby stał się problemem jednego parametru).

Problem polega na ocenie wielomianu Tutte wykresu G o współrzędnych (x, y). Możemy ograniczyć współrzędne do liczb całkowitych. Problem występuje w P, jeśli (x, y) jest jednym z punktów (1, 1), (-1, -1), (0, -1), (-1,0) lub spełnia (x-1 ) (y-1) = 1. W przeciwnym razie jest to # P-trudny.

Otrzymałem to z artykułu Wikipedii na temat wielomianu Tutte .

$k$$k=2$$2^d$$O(n^{4d-3})$$d \geq 2$$k$$2$

$t$

$t$$t$$G$$H$$G$$x$$y$$x$$y$$H$$t$$G$$t$$t$

Podzielonego wykres przedstawia wykres, którego wierzchołek zestaw może być podzielony na klika i niezależny zespół.

$t \ge 3$$t$

$k$

$k \ne \Delta$$NP$

W przypadku grafów sześciennych decydowanie o istnieniu kolorowania krawędzi za pomocą:

• $k=2$
• $k=3$$NP$
• $k \ge 4$

Holyer, Ian (1981), „The NP-zupełność kolorowania krawędzi”, SIAM Journal on Computing 10: 718–720

http://en.wikipedia.org/wiki/Edge_coloring

$\to$$\to$$\to$$\to \cdots$

$n$$n$$n$$n$

Dowód został ogłoszony w tym dokumencie .

$k$$k$

$G$$k=1$$G$$\sf NP$$k \in \{2,3\}$$\sf P$$k$

Patrz Chandran, L. Sunil, Deepak Rajendraprasad i Marek Tesař. „Tęczowe zabarwienie podzielonych wykresów”. nadruk arXiv arXiv: 1404.4478 (2014).

$U\subseteq V(G)$$G$$G[U]$$G-U$

Decyzja, czy wykres o średnicy 1 ma odłączony zestaw przekrojów, jest banalna. Problem staje się trudny do NP na wykresach o średnicy 2 patrz ten papier i znów jest łatwy na wykresach o średnicy co najmniej 3 patrz ten papier .