Zliczanie liczby osłon wierzchołków: kiedy jest to trudne?

Rozważmy problem # P-zupełny liczenia liczby osłon wierzchołków danego wykresu $G = (V, E)$ .

Chciałbym wiedzieć, czy jest jakikolwiek wynik pokazujący, jak twardość takiego problemu zmienia się w zależności od parametru (na przykład ).$G$$d = \frac{|E|}{|V|}$

Mam wrażenie, że problem powinien być łatwiejszy zarówno wtedy, gdy jest rzadki, jak i jest gęsty, podczas gdy powinien być trudny, gdy G jest „w środku”. Czy to naprawdę tak jest?$G$$G$$G$

Problem #VC obliczania liczby osłon wierzchołków danego wykresu pozostaje trudny do # P dla wykresów 3-regularnych; patrz na przykład [Greenhill, 2000].

Aby pokazać, że problem #VC pozostaje # P-trudno wykresach z co najwyżej $c\cdot n$ krawędzie, gdzie $n$ jest liczbą wierzchołków i $0<c<3/2$ , zmniejsza się od przypadku regularnego 3 przez dodanie wystarczająco dużą niezależny zestaw (o rozmiarze liniowym). Liczba osłon wierzchołków pozostaje taka sama, jeśli dodasz niezależny zestaw.

Podobnie, aby pokazać, że problem #VC pozostaje # P-trudno wykresach z co najmniej $c\cdot n^2$ krawędzi, gdzie $n$ jest liczbą wierzchołków i $0<c<1/2$ , z #VC zmniejszyć przez dodanie wystarczająco dużą element kliki (o wielkości liniowej). Liczba osłon wierzchołków jest mnożona przez $p+1$ jeśli dodasz do wykresu klikę o rozmiarze $p$ .

Catherine S. Greenhill: Złożoność liczenia kolorów i niezależnych zbiorów w rzadkich grafach i hipergraphach . Złożoność obliczeniowa 9 (1): 52-72 (2000)

Zgodnie z odpowiedzią Jarosława, Luby i Vigoda jako pierwsi pokazali FPRAS dla #IS w warunkach gęstości (maksymalny stopień 4, który, jak sądzę, jest słabszy niż wynik Weitza), podczas gdy Dyer, Frieze i Jerrum wykazali, że nie ma FPRAS dla #IS, jeżeli maksymalny stopień wykresu wynosi 25, chyba że RP = NP.

Bibliografia:

Martin Dyer, Alan Frieze i Mark Jerrum. O zliczaniu niezależnych zbiorów na rzadkich wykresach. FOCS 1999.

Michael Luby i Eric Vigoda. Około czterech. STOC 1997.

Zobacz także notatki z wykładu ETH Jerrum, „Liczenie, próbkowanie i integracja: algorytmy i złożoność”.

$n$$d$$d$$f(d,\epsilon)\cdot n$$\exp(\epsilon n)$$d$$2$-Sat (co odpowiada zliczaniu niezależnych zestawów i zliczaniu pokryw wierzchołków).

$n$$\exp(o(n))$

Zestaw jest pokrywą wierzchołków, a jego uzupełnieniem jest zbiór niezależny, dlatego ten problem jest równoważny zliczaniu zbiorów niezależnych.

Algebraiczne zliczanie niezależnych zbiorów to FPT dla wykresów ograniczonej ograniczonej szerokości kliki. Zobacz na przykład „Wielomianowy wielomian z przeplotem i jego obliczenia dla wykresów ograniczonej szerokości kliki”, gdzie obliczają uogólnienie wielomianu niezależności. Dodanie współczynników wielomianu niezależności daje liczbę niezależnych zbiorów.

Wykresy z maksymalnym stopniem 3 mogą mieć nieograniczoną szerokość kliki.

$d$$\lambda$

_{(źródło: yaroslavvb.com )}

$\lambda=1$

$d$$\lambda$$d$