An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: A Simple FPTAS for Counting Edge Covers and Generating Edge Covers of Path Graphs. However, unless I missed something, they do not provide a reference for this claim, or a proof. (Reference 3 of the first paper seemed promising, but I didn't find what I wanted there either.)

Where can I find a reference or proof of the fact that counting the number of edge covers of a graph is #P-complete?

I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems.

EdgeCover is included in the dichotomy theorem in (1). Theorem 6.2 (in the journal version or Theorem 6.1 in the preprint) shows that EdgeCover is #P-hard over planar 3-regular graphs. To see this, the expression for EdgeCover as a Holant problem over 3-regular graphs is $\operatorname{Holant}([0,1,1,1])$ (or replace $[0,1,1,1]$ with $[0,1,\dotsc,1]$ containing $k$ 1's for the same problem over $k$-regular graphs). This $[0,1,1,1]$ notation lists the output of a symmetric function in order of input Hamming weight. For some subset of the set edges (which we think of as being assigned 1 and the complement set being assigned 0), the constraint at each vertex is that at least one edge is assigned 1, which is exactly what the function $[0,1,1,1]$. For a fixed subset of edges, its weight is the product of the outputs of $[0,1,1,1]$ at each vertex. If any vertex is not covered, it contributes a factor of $0$. If all vertices are covered, then all vertices contribute a factor of $1$, so the weight is also $1$. Then the Holant is to sum over every possible subset of edges and add the weight corresponding to each subset. This Holant value is exactly the same if we subdivide every edge and impose the constraint that both incident edges to these new vertices must be equal. Using the symmetric function notation, this binary equality function is $[1,0,1]$. This graph is bipartite. The vertices in one part have the $[0,1,1,1]$ constraint while the vertices in the other part have the $[1,0,1]$ constraint. The expression for this as a Holant problem is $\operatorname{Holant}([0,1,1,1]|[1,0,1])$. Then you can check for yourself that row "$[0,1,1,1]$" and column "$[1,0,1]$" of the table near the theorem cited above contains "H", which means the problem is #P-hard even the input graph must be planar.

Side note: Note that Pinyan Lu is an author of both this paper and the first paper you cite. I am guessing that when their paper says "counting edge covers is a #P-complete problem even when we restrict the input to 3 regular graphs", they were implicitly citing (1). They probably didn't mention that the hardness also holds when further restricted to planar graphs since their FPTAS does not need this restriction.

Later Holant dichotomy theorems, such as those in (2,3)---conference and journal versions of the same work---proved more. Theorem 1 (in both versions) says that EdgeCover is #P-hard over planar $k$-regular graphs for $k \ge 3$. To see this, we need to apply a holographic transformation. As described above, the expression for EdgeCover as a Holant problem over $k$-regular graphs is $\operatorname{Holant}([0,1,\dotsc,1])$, where $[0,1,\dotsc,1]$ contains $k$ 1's. And furthermore, this is equivalent to $\operatorname{Holant}([1,0,1]|[0,1,\dotsc,1])$. Now we apply a Holographic transformation by $T = \begin{bmatrix} 1 & e^{\pi i / k} \\ 1 & 0 \end{bmatrix}$ (or its inverse, depending on your perspective). By Valiant's Holant Theorem (4,5), this does not change the complexity of the problem (in fact, both problems are actually the same problem because they agree on the output of every input...only the expression of the problem has changed). The alternate expression for this problem is

$$ \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), $$ where $=_k$ is the equality function on $k$ inputs. To apply Theorem 1, we have to normalize $[2, e^{\pi i / k}, e^{2 \pi i / k}]$ to $[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

  • Wow, thanks for pointing me to this and for taking the time to explain the vocabulary and connection to edge cover! I agree with you that (1) implicitly proves that EdgeCover is hard (and is hard even for 3-regular planar graphs). I'm also interested to know if anyone proved the #P-hardness of EdgeCover before (1), though I'm already quite happy that I have something to cite if I need to use this result (which was my main concern when asking). Thanks again for your answer! – a3nm Mar 2 '14 at 18:01
up vote 3 down vote accepted

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.

Note that these results do not capture the result in Tyson Williams' answer, where we can additionally assume that the input graphs are planar and 3-regular.

References:

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.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.