Twardość problemów FPT

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?

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 .( x , k ) Q f ( k ) | x | O ( 1 )$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.k k k O ( 2 k n 2 ) $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 wn ℓ G n - ℓ O ( 2 n - ℓ n 2 ) ℓ n n - ℓ $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$

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 n - 2 k 2 $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 .k W [ 1 $n-k$$k$$W[1]$

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.

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 ( n 2 ) k $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!

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.