Twardość problemów FPT

13

Osłonę wierzchołka można łatwo zredukować do zestawu niezależnego i odwrotnie.

Jednak w kontekście sparametryzowanej złożoności zestaw niezależny jest trudniejszy niż osłona wierzchołka. Jądro z wierzchołków istnieje problem pokrycia wierzchołkowego, ale niezależnego zestawu jest biała 1 dysku. $2k$

Jak zmienia się natura Independent Set w kontekście FPT i dlaczego?

cc.complexity-theory parameterized-complexity fixed-parameter-tractable

— Nikhil
źródło

9

Główna idea odpowiedzi: jeśli zredukujemy wystąpienie sparametryzowanego zestawu niezależnego do sparametryzowanej osłony wierzchołków, wówczas parametr, z którym skończymy, zależy od wielkości wykresu i nie zależy tylko od parametru wejściowego. Teraz trochę więcej szczegółów.

Jak wiadomo, sparametryzowany problem występuje w (jednolitym) FPT, jeśli istnieje algorytm, który decyduje, czy dane wejściowe są zawarte w w czasie dla jakaś funkcja . $Q$ $(x,k)$ $Q$ $f(k) |x|^{O(1)}$ $f$

Ponieważ możesz zdecydować, czy wykres ma osłonę wierzchołka o rozmiarze , wybierając krawędź i rozgałęzienie, na którym z dwóch punktów końcowych umieścić w pokrywie wierzchołka, rozgałęzienie to ma głębokość (w przeciwnym razie wstawiłeś więcej niż wierzchołki w okładce) i łatwo biegnie w czasie ; dlatego Vertex Cover jest w FPT. $G$ $k$ $k$ $k$ $O(2^k n^2)$ $k$

Załóżmy teraz, że chcemy spróbować użyć tego algorytmu, aby pokazać, że sparametryzowany niezależny zestaw znajduje się w FPT; Załóżmy, że otrzymaliśmy wykres na wierzchołkach i chcemy zdecydować, czy ma on niezależny zestaw wielkości . Jest to równoważne z pytaniem, czy ma pokrycie wierzchołków o rozmiarze . Używamy więc powyższego algorytmu do obliczenia odpowiedzi w czasie . W naszym algorytmie FPT funkcja wykładnicza w czasie wykonywania może zależeć od parametru, którym jest , ale NIE może zależeć od wielkości wejścia, która wynosi ; ale podejście, które zarysowaliśmy, wykorzystuje wykładniczy czas w $G$ $n$ $\ell$ $G$ $n - \ell$ $O(2^{n - \ell} n^2)$ $\ell$ $n$ $n - \ell$ i dlatego nie jest parametrem FPT w odniesieniu do parametru . Dlatego fakt, że Osłona Wierzchołków jest w FPT, nie oznacza, że Independent Set jest w FPT. $\ell$

— Bart Jansen
źródło

Dziękuję za wszystkie odpowiedzi. W kontekście sparametryzowanej złożoności rozumiem ten pomysł, gdy próbuję zbadać twardość zbioru Independent, rozumując na podstawie Vertex Cover. Nie znalazłem jednak żadnego wyjaśnienia, które dotyczyłoby Independent Set, niezależnie od kontekstu okładki Vertex? Czy jest coś w strukturze (lub przyrodzonej naturze) znalezienia Niezależnego Zestawu, co czyni go trudniejszym?

— Nikhil

Bart, dlaczego nie ma parametru dla którego redukcja działa zgodnie z oczekiwaniami?

k

$k$

— Raphael

@Raphael: Czy możesz wyjaśnić swoje pytanie? Te tylko parametry „dozwolone” przez pytanie PO są odpowiednie rozmiary rozwiązanie. Jeśli pozwolimy na dowolne parametry, to dla wielu istnieje redukcja, która działa zgodnie z potrzebami (jeśli poprawnie zrozumiałem to zdanie): Na przykład, jeśli zachowamy parametr jako „rozmiar minimalnej wielkości osłony wierzchołków” dla obu problemów, wówczas oba są FPT; MinVC według argumentu Barta i MaxIndSet według tego samego argumentu i przy użyciu redukcji PO. Dopiero gdy nalegamy, aby parametr MaxIndSet był jego wielkością rozwiązania, problem staje się twardy [1].

— gphilip

Doskonale rozumiesz moje pytanie! W tym sensie pytanie PO jest źle postawione: sensowne jest mówienie o sparametryzowanej złożoności dla par (nieparametrycznego) problemu i parametru. Mentalnie wypełniłem lukę „forallem”, co oznacza, że przeczytałem odpowiedź Barta również w sensie „for all ” i pomyślałem, że jest ona błędna / niepełna. Dlatego moje pytanie. Nawiasem mówiąc, inne odpowiedzi mają ten sam problem. Najwyraźniej wszyscy oprócz mnie wypełniają lukę kanonicznym wyborem.

k

$k$

— Raphael

6

Nie powiedziałbym, że „natura” problemu zmienia się, cokolwiek to ma znaczyć. Wszystko, co się zmienia, to parametr, czyli sposób, w jaki mierzysz trudność problemu.

Wykresy, których pokrycie wierzchołków ma wielkość co najwyżej są tak skonstruowane, że można skutecznie zmniejszyć ich rozmiar: Możemy łapczywie znaleźć maksymalne dopasowanie wielkości co najwyżej a reszta wykresu jest co najmniej niezależnym zestawem wielkości . Stosując reguły redukcji, takie jak redukcja korony, liczbę wierzchołków można zmniejszyć maksymalnie do . $k$ $k$ $n-2k$ $2k$

Z drugiej strony wykresy, które mają okładki wierzchołków o rozmiarze co najwyżej (lub równoważnie, maksymalne niezależne mają rozmiar co najmniej ), nie wydają się mieć tak prostej struktury. Można to sprecyzować, jak zauważyłeś : ich struktura pozwala nam zakodować dowolny problem . $n-k$ $k$ $W[1]$

— Holger
źródło

4

Poniższe informacje mogą dać intuicję dla tej różnicy. Podzbiór wierzchołków S jest pokrywą wierzchołków G = (V, E) wtedy i tylko wtedy, gdy VS jest niezależnym zestawem, więc jeśli MVC jest wielkością minimalnej osłony wierzchołków, wówczas MIS = | V | -MVC jest wielkością maksymalny niezależny zestaw. Algorytm FPT sparametryzowany przez X umożliwia wykładniczy czas działania w funkcji X. Losowy wykres na n wierzchołkach z prawdopodobieństwem krawędzi o połowę ma z wysokim prawdopodobieństwem MIS o wielkości około 2logn i MVC o wielkości około n-2logn. Zatem przynajmniej dla tych wykresów algorytm FPT sparametryzowany przez MVC po prostu pozwala na znacznie więcej czasu niż jeden sparametryzowany przez MIS.

4

Chociaż zgadzam się z tym, co powiedzieli inni, innym sposobem, który wydaje mi się pomocny, gdy myślę o tych rzeczach, jest przekształcenie problemu jako problemu rozpoznawania, tj. „Czy wykres wejściowy należy do rodziny grafów, które mają co najwyżej k pokrycie wierzchołków?” / „Czy wykres wejściowy należy do rodziny grafów, które mają niezależnie ustawione co najmniej k?”.

Intuicyjnie, bardziej ograniczona rodzina grafów powinna być łatwiejsza do rozpoznania niż bogatsza, bardziej ogólna. Rodzina wykresów pokrycia wierzchołków co najwyżej k jest bardzo ograniczona, w rzeczywistości każdy taki wykres można opisać tylko za pomocą bitów , co jest znacznie mniejsze niż zwykłe potrzebne bity, przy założeniu, że k jest znacznie mniejsze niż n. Z drugiej strony rodzina wykresów niezależnego zestawu co najmniej k jest bardzo bogata: każdy wykres można edytować, aby do niego należał, usuwając co najwyżej krawędzie. $O(k^2+2^k\log n)$ $O(n^2)$ $k^2$

Dla mnie jest to jedno intuicyjne wyjaśnienie, dlaczego spodziewałbym się, że łatwiej będzie rozpoznać małą pokrywę wierzchołków niż mały niezależny zestaw. Oczywiście powinno być oczywiste, że powyższe myśli nie są zbliżone do formalnego argumentu i wydaje mi się, że pod koniec dnia najbardziej przekonującym dowodem na to, że rzeczywiście trudniej jest rozpoznać niezależny zestaw wielkości k, jest właśnie twardość W niezależnego zestaw!

— Michael Lampis
źródło

W jaki sposób usunięcie krawędzi wystarcza, aby dać wykresowi niezależny zestaw wierzchołków? Myślę, że będziesz potrzebować usuwania krawędzi, jeśli chcesz uzyskać niezależny zestaw rozmiaru na pełnym wykresie na wierzchołkach.

k^{2}

$k^2$

k

$k$

(\binom{k}{2}) + k \cdot (n - k - 1)

$\binom{k}{2} + k \cdot (n - k - 1)$

k

$k$

n

$n$

— Bart Jansen

@Bart: W przypadku niezależnego zestawu wierzchołków musisz tylko upewnić się, że nie ma żadnej krawędzi między tymi wierzchołkami , a co najwyżej krawędzie w (prostym) podrozdziale zamówienia .

k

$k$ $k$

k \cdot (k - 1) \leq k^{2}

$k \cdot (k-1) \leq k^2$

k

$k$

— Mathieu Chapelle,

3

To jest bardzo pośrednia odpowiedź i może nie do końca odpowiedzieć na twoje obawy. Ale FPT i hierarchia W są ściśle powiązane z zbliżalnością (problemy FPT często mają PTAS itp.). W tym kontekście należy zauważyć, że dla każdego wykresu VC = n - MIS, a zatem przybliżenie dla VC nie daje przybliżenia dla MIS. Dlatego potrzebujesz przybliżonych wartości L-redukcji. Podejrzewam, że istnieje równoważne pojęcie „redukcji zachowania jądra” również dla sparametryzowanej złożoności.

— Suresh Venkat
źródło

Czy w FPT istnieje pojęcie „redukcji zachowywania jądra”?

— Nikhil

Nie wiem: stąd cytaty :). Czekam na sparametryzowanych ekspertów od złożoności.

— Suresh Venkat

2

Właśnie to przywołałeś! ;)

— Raphael

4

Istnieje takie pojęcie: wielomianowa transformacja czasu i parametru. Problem sparametryzowany P wielomian czas-i-parametr przekształca się w Q (czytaj: ), jeśli istnieje algorytm wielomianowy, który dał wystąpienie problemu , wyprowadza się w czasie wielomianowym równoważne przykład w tak, że . Użycie do jądra jest następujące: jeśli , ma jądro wielomianowe, a klasyczne wersje i są NP-kompletne, to ma również jądro wielomianowe . (

P \leq_{p t p} Q

$P \leq _{ptp} Q$

(x, k)

$(x,k)$

P

$P$

(x^{'}, k^{'})

$(x', k')$

Q

$Q$

k^{'} \in k^{O (1)}

$k' \in k^{O(1)}$

P \leq_{p t p} Q

$P \leq_{ptp} Q$

Q

$Q$

P

$P$

Q

$Q$

P

$P$ dx.doi.org/10.1007/978-3-642-04128-0_57 )

— Bart Jansen

Innym dokumentem stwierdzającym pewne relacje między przybliżalnością a FPT jest [ dx.doi.org/10.1016/S0020-0190(97)00164-6], gdzie pokazują, że jeśli problem jest W [1] trudny, to nie można przyznać wydajnego PTAS gdzie funkcja celu jest również parametrem. Wydajny PTAS ma złożoność czasową , podczas gdy złożoność czasowa jest niedozwolona. Ten sam wynik znajduje się również w pracy Bazgana.

O (2^{1 / ϵ} n^{k})

$O(2^{1/\epsilon}n^k)$

O (n^{1 / ϵ})

$O(n^{1/\epsilon})$

— Gianluca Della Vedova