Trudne do rozwiązania podkluczowe problemy z grafem twardym

W świetle ostatnich wyników Arory , Baraka i Steurera , Subexponential Algorytmy dla unikalnych gier i powiązanych problemów , interesują mnie problemy z grafem, które mają algorytmy czasu podwykładniczego, ale uważam, że nie jest to rozwiązanie wielomianowe. Znanym przykładem jest izomorfizm grafów, który ma algorytm subklonencjalny . Innym przykładem jest problem log-Clique, który można rozwiązać w quasi-wielomianowym czasie ( ). n O ( log n $2^{O(n^{1/2} \log n)}$$n^{O(\log n)}$

Szukam interesujących przykładów i najlepiej odniesienia do ankiet na temat podwykładniczych problemów z twardym grafem (niekoniecznie zupełnych). Ponadto, czy są jakieś problemy z wykresem niekompletnym z algorytmami subwykładniczego czasu?N $NP$$NP$

Impagliazzo, Paturi i Zane wykazali, że hipoteza czasu wykładniczego implikuje, że klikanie, k-kolorowalność i pokrycie wierzchołków potrzebują czasu.$2^{\Omega(n)}$

Nawiasem mówiąc, problem Max Clique, w całości, można rozwiązać w czasie gdzieNjest rozmiarem danych wejściowych.$2^{\tilde O(\sqrt N)}$$N$

Jest to trywialne, jeśli wykres jest reprezentowany przez macierz przylegania, ponieważ wtedy , a szukanie brutalnej siły zajmie czas 2 O ( | V | ) .$N=|V|^2$$2^{O(|V|)}$

Ale możemy uzyskać tę samą granicę, nawet jeśli wykres jest reprezentowany przez listy przyległości, za pomocą algorytmu czasu działania . Aby zobaczyć jak, zdobądźmy2 ˜ O ($2^{\tilde O(\sqrt{|V| + |E|})}$-Time algorytm dla NP-zupełny problemu decyzyjnego, w którym podano wykresG=(V,E)iki chcemy wiedzieć, czy istnieje klika rozmiaru≥k.$2^{\tilde O(\sqrt{|V| + |E|})}$$G=(V,E)$$k$$\geq k$

Algorytm po prostu usuwa wszystkie wierzchołki stopnia i zachodzące na nich krawędzie, a następnie robi to ponownie, i tak dalej, dopóki nie zostanie nam indukowany wierzchołkiem subgraph nad podzbiorem V ′ wierzchołków, każdy o stopniu ≥ k , lub z pustym wykresem. W tym drugim przypadku wiemy, że nie może istnieć żadna klika o rozmiarze ≥ k . W pierwszym przypadku przeprowadzamy wyszukiwanie siłowe z grubsza | V ′ | k . Zauważ, że | E | ≥ k ⋅ | V ′ | / 2 i k $< k$$V'$$\geq k$$\geq k$$|V'|^k$$|E| \geq k\cdot |V'| /2$, tak że | E | ≥ k 2 / 2 , a więc poszukiwanie brute-force działa w czasie | V ′ | k faktycznie działa w czasie 2 O ( $k\leq |V'|$$|E| \geq k^2/2$$|V'|^k$.$2^{O(\sqrt{|E|} \cdot \log |V|)}$

Ponieważ każdy płaski wykres na wierzchołkach ma szerokość O ( $n$wszystkie problemy, które można rozwiązać w czasieO∗(2 O ( k ) )dla wykresów szerokości co najwyżej ~k(istnieje wiele takich problemów) mają algorytmy czasu podwykładniczego na wykresach płaskich poprzez obliczenie współczynnika stałego aproksymacja do szerokości grzbietu w czasie wielomianowym (na przykład poprzez obliczenie szerokości gałęzi za pomocą algorytmu ratcatcher), a następnie uruchomienie algorytmu długości grzbietu, co daje czas działania postaciO∗(2 O ( $O(\sqrt{n})$$O^*(2^{O(k)})$$k$dla wykresów nanwierzchołkach. Przykładami są Planarny zestaw niezależny i Planarny zestaw dominujący, które oczywiście są NP-kompletne.$O^*(2^{O(\sqrt{n})})$$n$

Istnieje ścisły związek między sub wykładniczym rozwiązaniem czasowym (SUBEPT) a ustaloną ciągliwością parametrów (FPT). Łącze między nimi podano w poniższym artykule.

Izomorfizm między podwykładniczą i sparametryzowaną teorią złożoności , Yijia Chen i Martin Grohe, 2006.

W skrócie, wprowadzili pojęcie zwane mapowaniem miniaturyzacji , które mapuje sparametryzowany problem na inny sparametryzowany problem ( Q , κ ) . Widząc normalny problem jako problem sparametryzowany przez rozmiar wejściowy, mamy następujące połączenie. (Zobacz twierdzenie 16 w pracy)$(P,\nu)$$(Q,\kappa)$

Twierdzenie . jest w SUBEPT iff ( Q , κ ) jest w FPT.$(P,\nu)$$(Q,\kappa)$

Uważaj na definicje tutaj. Zwykle patrzymy na problem kliki sparametryzowany w k , więc nie ma algorytmu sub-wykładniczego czasu, który zakłada hipotezę wykładniczego czasu. Ale tutaj pozwalamy sparametryzować problem na podstawie wielkości wejściowej O ( m + n ) , dlatego problem można rozwiązać za pomocą 2 O ( $k$$k$$O(m+n)$, który jest sub wykładniczym algorytmem czasu. Twierdzenie to mówi nam, żeproblem klikikjest stałym parametrem możliwym do przełknięcia pod pewnym skrętem parametruk, co jest rozsądne.$2^{O(\sqrt{m}\log m)}$$k$$k$

Ogólnie rzecz biorąc, problemy w SUBEPT w ramach redukcji SERF (rodziny redukcji sub wykładniczej) mogą zostać przekształcone w problemy w FPT w ramach redukcji FPT. (Twierdzenie 20 w pracy) Ponadto połączenia są jeszcze silniejsze, ponieważ dostarczyły one twierdzenia o izomorfizmie między całą hierarchią problemów w wykładniczej teorii złożoności czasowej i sparametryzowanej teorii złożoności. (Twierdzenie 25 i 47) Chociaż izomorfizm nie jest kompletny (między nimi brakuje pewnych powiązań), dobrze jest mieć jasny obraz tych problemów, a my możemy badać algorytmy sub-wykładnicze za pomocą sparametryzowanej złożoności.

Aby uzyskać więcej informacji, zobacz ankietę Jörga Fluma i Martina Grohe oraz redaktora kolumny złożoności Jacobo Torána.

innym przykładem może być gra Cop i Robber, która jest trudna do pokonania, ale można ją rozwiązać w czasie na wykresach z n wierzchołkami. Zapis bibliograficzny BibTeX w XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Ściganie szybkiego rabusia na wykresie. Teoria Comput. Sci. 411 (7-9): 1167-1181 (2010)$2^{o(n)}$

Najlepszy algorytm aproksymacji dla kliki daje niewiarygodnie zły współczynnik aproksymacji (należy pamiętać, że współczynnik aproksymacji n jest trywialny).$n/\text{polylog } n$$n$

Istnieją twardości wyników aproksymacji przy różnych założeniach twardości, które nie do końca pasują do tego, ale wciąż dają twardość . Osobiście uważam, że przybliżenie n / polylog  n dla kliki jest tak dobre, jak by to zrobiły algorytmy wielomianowe.$n^{1-o(1)}$$n/\text{polylog } n$

Ale przybliżenie dla kliki można łatwo wykonać w czasie quasi-wielomianowym.$n/\text{polylog } n$

Problem trudny dla NP to problem, który ma redukcję czasu wielomianowego względem SAT. Nawet jeśli SAT potrzebuje czasu , może to przełożyć się na czas 2 Ω ( N ϵ ) dla problemu, do którego redukujemy. Jeśli ten ostatni ma wielkość wejściową N, może się zdarzyć, że N = n 1 / ϵ dla małej stałej ϵ .$2^{\Omega(n)}$$2^{\Omega(N^\epsilon)}$$N=n^{1/\epsilon}$$\epsilon$