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

14

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 jest „w środku”. Czy to naprawdę tak jest? $G$ $G$ $G$

— Giorgio Camerani
źródło

Czy chcesz policzyć wszystkie osłony wierzchołków, czy wszystkie minimalne osłony wierzchołków? Zauważ, że pierwszy problem może być w niektórych przypadkach łatwiejszy, ponieważ niekoniecznie pomaga rozwiązać problem NP-zupełny.

— Ryan Williams,

Cześć Ryan, tak, chcę policzyć wszystkie osłony wierzchołków. Dlaczego mówisz „niekoniecznie pomaga ci rozwiązać problem NP-zupełny” ? Jeśli jest to # P-complete, dlaczego nie pomaga mi to w rozwiązywaniu problemów z NP-complete?

— Giorgio Camerani,

@Walter, Liczenie przypisań zmiennych, które spełniają daną formułę 2SAT, to # P-complete, ale 2SAT jest w P.

— Mohammad Al-Turkistany

@turkistany: Tak, już wiem, że ...

— Giorgio Camerani,

@turkistany: ... ale potem? Jakikolwiek problem NP-zupełny mam, mogę przekonwertować go na SAT, następnie SAT na #SAT, a następnie #SAT na # Monotone-2SAT (co jest dokładnie takie samo jak liczenie pokryw wierzchołków). Dlaczego więc nie powinienem być w stanie rozwiązać problemów z NP-zupełnością, biorąc pod uwagę możliwość liczenia osłon wierzchołków?

— Giorgio Camerani,

15

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)

— Serge Gaspers
źródło

Więc wnioskiem jest to, że #VC dla wykresów sześciennych jest # P-kompletny, ponieważ #IS jest # P-kompletny?

— delete000

9

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ść”.

— RJK
źródło

4

BTW, Alan Sly udowodnił, że czas wielomianowy jest niedopuszczalny dla maksymalnego stopnia = 6 - arxiv.org/abs/1005.5584

— Jarosław Bułatow

1

@Yaroslav: Dzięki za odniesienie. Wygląda na dobrą lekturę!

— RJK

9

$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))$

— Holger
źródło

w odniesieniu do twojego ostatniego komentarza: ETH oznacza, że SAT nie może być rozwiązany w czasie podwykonawczym, co przy standardowych redukcjach oznacza, że O NIEZALEŻNYM ZESTAWIE również nie można zdecydować w czasie podwykładniczym. Jest zatem natychmiastowe, że ETH zakłada, że zliczanie niezależnych zbiorów również nie może być wykonane w czasie podwykonawczym.

— András Salamon

1

\exp (o (n / \log^{3} n))

$\exp(o(n/\log^3 n))$

8

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$

λ < \frac{(Δ - 1)^{Δ - 1}}{(Δ - 2))^{Δ}}

$\lambda<\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^\Delta}$

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

$\lambda=1$

$d$ $\lambda$ $d$

— Jarosław Bułatow
źródło

Problem z pracą z IS zamiast z VC polega na tym, że wykresy dopełniacza mogą utracić pewne miłe właściwości, których się chce: na przykład „stopień ograniczony co najwyżej k” staje się „ze stopniem co najmniej nk”, który jest teraz zależny od wielkości instancji. To może, ale nie musi być istotne.

— András Salamon

@ András To zestaw wierzchołków jest skomplikowany, a nie zestaw krawędzi.

— Tyson Williams,