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

60

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 .kNkkk{1,2}k3k

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 gdyk=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 k0 ale NP-twardy dla k0+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!nnn=2k1n
  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 iG 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 ).H1H2H3HiGGi{1,3}i=2
mikero
źródło
3
Drobne poprawki - przykład (3): problem występuje w jeśli n jest liczbą całkowitą typu Mersenne'a, tj. N = 2 k - 1 dla pewnej liczby naturalnej k ; n nie musi być liczbą pierwszą. (Na przykład 2 11 - 1 nie jest liczbą pierwszą). O ile n nie ma tej postaci, problemem jest # P -kompletne. Pnn=2k1kn2111nP
Aaron Sterling
Dzięki @Aaron Sterling - odpowiednio poprawiłem ten przykład.
mikero
1
Ważna korekta - przykład (3): Formuły muszą być także monotoniczne, dwukrotne odczytywać i mieć klauzule wielkości , gdzie n = 2 k - 1 , aby były dostępne. Zostało to udowodnione przez Jin-Yi Cai i Pinyan Lu. To nie tak motywowało Valiant. Poprawił rozmiar klauzuli na 3, a następnie zmienił tylko moduł. Wiadomo, że ma twardą charakterystykę 0. Valiant wykazał twardość mod 2 i podatność na rozciąganie mod 7. Twardość mod 2 wynosi P = twardość # 2 P , a nie twardość # P. Nie wiem, jaką sparametryzowaną rodzinę problemów próbujesz opisać. kn=2k1P=#2P
Tyson Williams
1
Aby uzyskać więcej informacji na ten temat, w tym odniesienia do referatów , zobacz Holographic_algorithm # History na Wikipedii.
Tyson Williams
Obawy dotyczące przykład (4): Mam nadzieję, że oznacza to, że oznaczamy G bycia realizacja s -graph H . Ale jak możemy powiedzieć, że piramida theta pryzmat ? Zauważ, że mówimy o indukowanych podgrodzie, a nie podgrodzie. HGGsH
Cyriak Antony

Odpowiedzi:

25

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.GnnPGnGPGPPP

Ł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. SPTPST

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=GnP=

Aaron Roth
źródło
Czy mógłbyś wymienić (lub wskazać) nietrywialny przykład? Myślę, że znasz już niektóre. Ciekawe jest również, czy występują przejścia fazowe P NP P NP.
Cyriak Antony
20

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.Gk1kGGkGkGkkk

vb le
źródło
17

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Δ73Δ6

Powiązane pytanie omówiono tutaj .

Oleksandr Bondarenko
źródło
14

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)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 ) = 2diam(G)=3diam(G)=2

Austin Buchanan
źródło
+1 Ładna odpowiedź. Co jest dominującą kliką?
Mohammad Al-Turkistany
1
Tak jak się wydaje - dominujący zestaw, który jest również kliką .
Austin Buchanan
13

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)

Robin Kothari
źródło
7
Zjawisko to wynika tylko z tego, że równie dobrze możemy postrzegać k jako min (k, nk) i rozwiązać zbiór k-kliki lub zestawu k-indept (naprawdę ten sam problem). Jeśli pomyślimy o 0 <k <= n / 2 z tego powodu, złożoność rośnie ściśle w k.
Aaron Roth,
4
@Aaron: Obawiam się, że twój argument nie jest poprawny. Znalezienie kliki o rozmiarze n-k różni się znacznie od znalezienia niezależnego zestawu wielkości k. Musisz być zdezorientowany faktem, że znalezienie kliki rozmiaru k na wykresie G jest równoważne znalezieniu niezależnego zestawu wielkości k w uzupełnieniu G.
Tsuyoshi Ito,
Tsuyoshi: Tak, oczywiście. Chciałem powiedzieć, że WLOG, możesz założyć k <= n / 2, ponieważ jeśli nie, weź wykres dopełnienia i rozwiąż problem dla k '= nk. I oczywiście podkreśla to, że złożoność wzrasta w k.
Aaron Roth,
1
@Aaron: „jeśli nie, weź wykres dopełniacza i rozwiąż problem dla k '= nk.” To jest dokładnie nieprawidłowe twierdzenie, które próbuję sprzeciwić. Powtórzę to, co powiedziałem: „znalezienie kliki o rozmiarze k na wykresie G jest równoważne znalezieniu niezależnego zestawu wielkości k w uzupełnieniu G.” Znalezienie kliki o rozmiarze k na wykresie G nie jest równoznaczne ze znalezieniem klika o rozmiarze n-k w uzupełnieniu G.
Tsuyoshi Ito,
2
O tak. :-) To było głupie, wycofuję swój sprzeciw. To, co się tutaj dzieje, to tylko to, że dwumianowy [n, k] = Dwumianowy [n, nk], więc czas wyczerpującego poszukiwania rośnie monotonicznie dla k <n / 2, a monotoniczny maleje dla k> n / 2.
Aaron Roth,
12

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 .

Robin Kothari
źródło
12

kk=22dO(n4d3)d2k2

Kevin Costello
źródło
10

t

ttGHGxyxyHtGtt

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

t3t

użytkownik13136
źródło
10

k

kΔNP

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

  • k=2
  • k=3NP
  • k4

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

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

Mohammad Al-Turkistany
źródło
Czy mógłbyś dodać referencję?
Oleksandr Bondarenko
10

nnnn

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

użytkownik13136
źródło
6

UV(G)GG[U]GU

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 .

użytkownik13136
źródło