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 .
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:
- -kolorowalność płaskich wykresów: w P, z wyjątkiem gdy , gdzie jest NP-kompletna.
- Drzewo Steinera z zaciskami : W P, gdy (zwalnia się do najkrótszej ścieżki - ), a gdy (zapada się do MST), ale NP-twarde „pomiędzy”. Nie wiem, czy te przejścia fazowe są ostre (np. P dla ale NP-twardy dla ). Również przejścia zależą od wielkości instancji wejściowej, w przeciwieństwie do moich innych przykładów.
- Zliczanie zadowalające Przyporządkowanie płaską wzorze modulo W P, gdy n jest Mersenne
pierwszaliczba n = 2 k - 1 i # P kompletne do(?) Większość /wszystkie inne wartości N (Aaron Sterling, w tym nici ) . Wiele przejść fazowych! - 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 ).
Odpowiedzi:
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.Gn n P⊆Gn G P G∈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⊂P⊂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=Gn P=∅
źródło
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≥1 k G Gk Gk G k k k
źródło
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.Δ Δ=2 Δ⩾7 3⩽Δ⩽6
Powiązane pytanie omówiono tutaj .
źródło
Określanie, czy wykres ma dominującą klikę dla:G
Przypadek wynika z Brandstädta i Kratscha , a przypadek jest odnotowany w moim ostatnim artykule .d i a m ( G ) = 2diam(G)=3 diam(G)=2
źródło
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(nk) O(nc)
źródło
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 .
źródło
źródło
Podzielonego wykres przedstawia wykres, którego wierzchołek zestaw może być podzielony na klika i niezależny zespół.
źródło
W przypadku grafów sześciennych decydowanie o istnieniu kolorowania krawędzi za pomocą:
Holyer, Ian (1981), „The NP-zupełność kolorowania krawędzi”, SIAM Journal on Computing 10: 718–720
http://en.wikipedia.org/wiki/Edge_coloring
źródło
Dowód został ogłoszony w tym dokumencie .
źródło
Patrz Chandran, L. Sunil, Deepak Rajendraprasad i Marek Tesař. „Tęczowe zabarwienie podzielonych wykresów”. nadruk arXiv arXiv: 1404.4478 (2014).
źródło
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 .
źródło