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?


2 Answers 2


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

  • $\begingroup$ 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! $\endgroup$
    – a3nm
    Mar 2, 2014 at 18:01
  • 2
    $\begingroup$ @Tyson Williams: if you start from a 2-3-regular graph and contract the nodes of the partition of degree 2 then you could end up with a 3-regular multigraph, i.e., with parallel edges. Can this be fixed to show hardness on 3-regular simple graphs? More generally, this question could be asked for all the results on Holant problems, so I created a new question here cstheory.stackexchange.com/q/43912/38111, because I think the issue is not restricted to this particular problem (counting edge covers). I'd be glad if you could take a look :) $\endgroup$
    – M.Monet
    May 18, 2019 at 18:13
  • $\begingroup$ Ah, yes. Good observation. I am unable to remember right now what results there are for simple graphs. $\endgroup$ May 18, 2019 at 23:47
  • 1
    $\begingroup$ @TysonWilliams: Thanks for confirming, and no worries! In my community "graph" always means "simple graph" unless stated otherwise, so I hadn't stated it explicitly in the question. $\endgroup$
    – a3nm
    Aug 9, 2019 at 9:19
  • 1
    $\begingroup$ @TysonWilliams: after all, we have found how to get a hardness result on counting edge covers for simple graphs (that are 2-3 regular bipartite and planar) via holographic means. The details are in the latest version of my answer below, and in Appendix D of arxiv.org/abs/1703.03201. We use the hardness of counting vertex covers on 3-regular bipartite planar graphs from xia2006regular: these graphs have no self-loops, we subdivide each edge which removes parallel edges, and cai2008holographic does not create problems. (As for 3-regular graphs, as in your answer, we don't know.) $\endgroup$
    – a3nm
    Aug 28, 2019 at 12:00

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.


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

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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