Złożoność zliczania liczby okładek krawędzi wykresu

Osłona krawędzi jest podzbiorem krawędzi wykresu, tak że każdy wierzchołek wykresu sąsiaduje z co najmniej jedną krawędzią okładki. Poniższe dwa artykuły mówią, że liczenie krawędzi jest zakończone #P : Prosty FPTAS do zliczania krawędzi i generowania krawędzi krawędzi wykresów ścieżek . Jednakże, chyba że coś przeoczyłem, nie zawierają one odniesienia do tego roszczenia ani dowodu. (Odniesienie 3 pierwszego artykułu wydawało się obiecujące, ale nie znalazłem tam również tego, czego chciałem).

Gdzie mogę znaleźć odniesienie lub dowód na to, że zliczanie okładek krawędzi wykresu jest # P-ukończone?

Nie wiem, gdzie to zostało po raz pierwszy udowodnione, ale ponieważ EdgeCover ma wyrażenie jako boolowski problem Holanta, jest on uwzględniony w wielu twierdzeniach dychotomii Holanta.

EdgeCover jest zawarty w twierdzeniu o dychotomii w (1). Twierdzenie 6.2 (w wersji z czasopisma lub Twierdzenie 6.1 w przedruku) pokazuje, że EdgeCover ma twardość # P w stosunku do płaskich 3-regularnych wykresów. Do tego widać, wyrażenie EdgeCover jako Holant problem przez 3 regularnych wykresach jest (lub zastąpić [ 0 , 1 , 1 , 1 ] do [ 0 , 1 , ... , 1 ] zawierające k 1 dla tego samego problemu w stosunku do $\operatorname{Holant}([0,1,1,1])$$[0,1,1,1]$$[0,1,\dotsc,1]$$k$$k$-regularne wykresy). Ta notacja wymienia dane wyjściowe funkcji symetrycznej w kolejności wejściowej masy Hamminga. W przypadku niektórych podzbiorów zestawu krawędzi (które uważamy za przypisane 1 i zestawowi uzupełnień przypisanemu 0), ograniczenie na każdym wierzchołku polega na tym, że co najmniej jedna krawędź ma przypisaną wartość 1, co jest dokładnie funkcją [ 0 , 1 , 1 , 1 ] . W przypadku stałego podzbioru krawędzi jego waga jest iloczynem wyników [ 0 , 1 , 1 , 1 $[0,1,1,1]$$[0,1,1,1]$$[0,1,1,1]$na każdym wierzchołku. Jeśli jakikolwiek wierzchołek nie jest objęty, przyczynia się do . Jeśli wszystkie wierzchołki są pokryte, wówczas wszystkie wierzchołki mają współczynnik 1 , więc ciężar również wynosi 1 . Następnie Holant ma zsumować każdy możliwy podzbiór krawędzi i dodać wagę odpowiadającą każdemu podzbiorowi. Ta wartość Holanta jest dokładnie taka sama, jeśli podzielimy każdą krawędź i narzucimy ograniczenie, że obie krawędzie padające na te nowe wierzchołki muszą być równe. Korzystając z notacji funkcji symetrycznej, ta funkcja równości binarnej wynosi [ 1 , 0 , 1 ] . Ten wykres jest dwustronny. Wierzchołki w jednej części mają [ 0 , 1 $0$$1$$1$$[1,0,1]$ ograniczenie, podczas gdy wierzchołki w drugiej części mają ograniczenie [ 1 , 0 , 1 ] . Wyrażeniem tego jako problemu Holanta jest Holant ( [ 0 , 1 , 1 , 1 ] | [ 1 , 0 , 1 ] ) . Następnie możesz samodzielnie sprawdzić ten wiersz „ [ 0 , 1 , 1 , 1 ] ” i kolumnę „ [ 1 , $[0,1,1,1]$$[1,0,1]$$\operatorname{Holant}([0,1,1,1]|[1,0,1])$$[0,1,1,1]$ ”tabeli w pobliżu cytowanego powyżej twierdzenia zawiera„ H ”, co oznacza, że ​​problem jest trudny do #P, nawet wykres wejściowy musi być płaski.$[1,0,1]$

Uwaga dodatkowa: Zauważ, że Pinyan Lu jest autorem zarówno tego artykułu, jak i pierwszego artykułu, który cytujesz. Zgaduję, że kiedy ich artykuł mówi: „liczenie okładek krawędzi jest problemem # P-zupełnym, nawet jeśli ograniczamy wprowadzanie do 3 zwykłych wykresów”, niejawnie cytowali (1). Prawdopodobnie nie wspomnieli, że twardość obowiązuje również w przypadku dalszego ograniczenia do grafów płaskich, ponieważ ich FPTAS nie potrzebuje tego ograniczenia.

Późniejsze twierdzenia dychotomii Holanta, takie jak te w (2,3) --- wersje konferencyjne i dziennikowe tego samego dzieła --- okazały się więcej. Twierdzenie 1 (w obu wersjach) mówi, że EdgeCover ma twardość P w porównaniu do płaskich wykresów nieregularnych dla k ≥ 3 . Aby to zobaczyć, musimy zastosować holograficzną transformację. Jak opisano powyżej, wyrażenie dla EdgeCover jako problemu Holanta nad k- regularnymi grafami to Holant ( [ 0 , 1 , … , 1 ] ) , gdzie [ 0 , 1 , … , 1 ] zawiera $k$$k \ge 3$$k$$\operatorname{Holant}([0,1,\dotsc,1])$$[0,1,\dotsc,1]$$k$1. Co więcej, jest to równoważne z . Teraz zastosujemy transformację holograficzną przez T = [ 1 e π i / k 1 0$\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$$T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$(lub odwrotnie, w zależności od twojej perspektywy). Według Twierdzenia Holanta Valianta (4,5) nie zmienia to złożoności problemu (w rzeczywistości oba problemy są w rzeczywistości tym samym problemem, ponieważ zgadzają się co do wyników każdego wkładu ... zmieniło się tylko wyrażenie problemu ). Alternatywnym wyrażeniem tego problemu jest

$$\operatorname{Holant}([1,0,1] T^{\otimes 2}|(T^{-1})^{\otimes k} [0,1,\dotsc,1]) = \operatorname{Holant}([2, e^{\pi i / k}, e^{2 \pi i / k}]|=_k),$$ $=_k$$k$$[2, e^{\pi i / k}, e^{2 \pi i / k}]$$[2 e^{-\pi i / k}, 1, e^{\pi i / k}]$ by dividing the original function by $e^{\pi i / k}$, which doesn't change the complexity of the problem since this value is nonzero. Then the values $X$ and $Y$ in the statement of the theorem are $X = 2$ and $Y = -2^k - 1$. For $k \ge 3$, one can check that this problem, so thus EdgeCover as well, is #P-hard over planar $k$-regular graphs for $k \ge 3$.

Side note: One can also see this theorem and proof in Michael Kowalczyk's thesis.

I will continue my literature search to see EdgeCover was shown to be #P-hard before (1).

(1) Holographic Reduction, Interpolation and Hardness by Jin-Yi Cai, Pinyan Lu, and Mingji Xia (journal, preprint).

(2) A Dichotomy for $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions by Jin-Yi Cai and Michael Kowalczyk.

(3) Partition functions on $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions by Jin-Yi Cai and Michael Kowalczyk.

(4) Holographic Algorithms by Leslie G. Valiant

(5) Valiant’s Holant Theorem and matchgate tensors by Jin-Yi Cai and Vinay Choudhary

After some more literature search, it appears that the complexity of counting the edge covers in a graph was shown to be #P-complete in bordewich2008path, Appendix A.1. (This assumes arbitrary graphs as input, i.e., they cannot enforce any assumptions on the input graph, except that they observe that the minimal degree can be made arbitrarily large). (bordewich2008path further indicates that the result is claimed without proof in bubley1997graph.) This result predates those of Cai, Lu, and Xia referenced as (1) in Tyson Williams' answer, and it does not rely on holographic theory.

Specifically, the result relies on the #P-hardness of counting independent sets in 3-regular graphs shown in greenhill2000complexity (improving on the analogous result for graphs of degree at most 4 shown in vadhan1997complexity), and proves the result using the technique of bubley1997graph.

A stronger result, namely, the hardness of counting edge covers in a bipartite graph of degree at most four (further imposing that the edge set can be partitioned into four matchings) was studied independently in khanna2011queries, Appendix B.1, again without holographic tools. They rely on the hardness of counting independent sets in 3-regular bipartite graphs (shown in xia2006regular by a refinement of the interpolation method of vadhan1997complexity) and then they apply a refinement of the technique of bordewich2008path.

An even stronger result (hardness of counting edge covers in a bipartite 2-3 regular graph, i.e., a bipartite graph where all vertices on one side have degree 2 and all vertices on the other side have degree 3, which is additionally planar) can be shown using the results of xia2006regular and cai2008holographic. The explanations for this appear as Appendix D of the latest version of our PODS'17 paper. In this case, we checked rather carefully that the result holds for simple graphs, i.e., for graphs that have neither self-loops nor multi-edges (see the comments to Tyson Williams' answer).

For hardness on planar 3-regular graphs, an argument is given in Tyson Williams' answer, but it would seem that it allows multi-edges and self-loops in the graphs.

References:

• bordewich2008path: Magnus Bordewich, Martin Dyer, Marek Karpinski, Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs, 2008.
• bubley1997graph: Russ Bubley, Martin Dyer, Graph orientations with no sink and an approximation for a hard case of #SAT, 1997. No open-access version seems available online. :-(
• cai2008holographic: J. Cai, P. Lu, M. Xia, Holographic reduction, interpolation and hardness, 2008
• greenhill2000complexity: Catherine Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs, 2000
• khanna2011queries: Sanjeev Khanna, Sudeepa Roy, Val Tannen, Queries with Difference on Probabilistic Databases, 2011.
• vadhan1997complexity: Salil P. Vadhan, The Complexity of Counting in Sparse, Regular, and Planar Graphs, 1997. Some results probably originally appeared in a thesis, but I didn't check.
• xia2006regular: Mingji Xia, Wenbo Zhao, #3-Regular Bipartite Planar Vertex Cover is #P-Complete, 2006. No open-access version seems available online. :-( Note that the first author is also an author of (1) in Tyson Williams' answer.

Diclaimer: I only had a superficial look at these papers and I am not an expert in this field, so there may be errors in my summary above.

Thanks to an anonymous PODS'17 referee for pointing me to khanna2011queries, which is what prompted me to write this answer.