<p>After some more literature search, it appears that <strong>the complexity of counting the edge covers in a graph was shown to be #P-complete in bordewich2008path, Appendix A.1</strong>. (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.</p>

<p>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.</p>

<p>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.</p>

<p>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 <a href="https://arxiv.org/abs/1703.03201" rel="nofollow noreferrer">latest version of our PODS'17 paper</a>. In this case, we checked rather carefully that the result holds for <em>simple</em> graphs, i.e., for graphs that have neither self-loops nor multi-edges (see the comments to Tyson Williams' answer).</p>

<p>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.</p>

<p>References:</p>

<ul>
<li>bordewich2008path: Magnus Bordewich, Martin Dyer, Marek Karpinski, <em><a href="http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2005/85262-CS.pdf" rel="nofollow noreferrer">Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs</a></em>, 2008.</li>
<li>bubley1997graph: Russ Bubley, Martin Dyer, <em>Graph orientations with no sink and an approximation for a hard case of #SAT</em>, 1997. No open-access version seems available online. :-(</li>
<li>cai2008holographic: J. Cai, P. Lu, M. Xia, <em><a href="http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf" rel="nofollow noreferrer">Holographic reduction, interpolation and hardness</a></em>, 2008</li>
<li>greenhill2000complexity: Catherine Greenhill, <em><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.467.3100&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">The complexity of counting colourings and independent sets
in sparse graphs and hypergraphs</a></em>, 2000</li>
<li>khanna2011queries: Sanjeev Khanna, Sudeepa Roy, Val Tannen, <em><a href="https://users.cs.duke.edu/~sudeepa/VLDB11-probdb-difference.pdf" rel="nofollow noreferrer">Queries with Difference on Probabilistic Databases</a></em>, 2011.</li>
<li>vadhan1997complexity: Salil P. Vadhan, <em><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.2294&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">The Complexity of Counting in Sparse, Regular,
and Planar Graphs</a></em>, 1997. Some results probably originally appeared in a thesis, but I didn't check.</li>
<li>xia2006regular: Mingji Xia, Wenbo Zhao, <em>#3-Regular Bipartite Planar Vertex Cover is #P-Complete</em>, 2006. No open-access version seems available online. :-( Note that the first author is also an author of (1) in Tyson Williams' answer.</li>
</ul>

<p><em>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.</em></p>

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

CC BY-SA 4.0
2017-02-28T00:11:54.857Z
2019-08-28T11:54:13.027Z
2019-08-28T11:54:13.027Z
Antoine Amarilli 'a3nm'
<p>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.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Symmetric_function" rel="noreferrer">symmetric function</a> 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.</p>

<p>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.</p>

<p>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 &amp; e^{\pi i / k} \\ 1 &amp; 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</p>

<p>$$
\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$.</p>

<p>Side note: One can also see this theorem and proof in <a href="http://cs.nmu.edu/~mkowalcz/research/main.pdf" rel="noreferrer">Michael Kowalczyk's thesis</a>.</p>

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

<p>(1) Holographic Reduction, Interpolation and Hardness by Jin-Yi Cai, Pinyan Lu, and Mingji Xia (<a href="http://link.springer.com/article/10.1007/s00037-012-0044-6" rel="noreferrer">journal</a>, <a href="http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf" rel="noreferrer">preprint</a>).</p>

<p>(2) <a href="http://link.springer.com/chapter/10.1007/978-3-642-13562-0_30" rel="noreferrer">A Dichotomy for $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions</a> by Jin-Yi Cai and Michael Kowalczyk.</p>

<p>(3) <a href="http://www.sciencedirect.com/science/article/pii/S0304397513000091" rel="noreferrer">Partition functions on $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions</a> by Jin-Yi Cai and Michael Kowalczyk.</p>

<p>(4) <a href="http://epubs.siam.org/doi/abs/10.1137/070682575" rel="noreferrer">Holographic Algorithms</a> by Leslie G. Valiant</p>

<p>(5) <a href="http://www.sciencedirect.com/science/article/pii/S0304397507004574" rel="noreferrer">Valiant’s Holant Theorem and matchgate tensors</a> by Jin-Yi Cai and Vinay Choudhary</p>

CC BY-SA 3.0
2014-03-02T18:01:05.083Z
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!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-08-07T15:43:20.100Z
OK, so if I understand correctly, @M.Monet's comment means that Holant-based techniques only apply to multigraphs, not graphs. So as far as I can tell, if one wants a proof that counting edge covers on graphs is #P-hard, one should cite bordewich2008path (cf my own answer) -- Tyson's answer in fact does not establish hardness of the right problem.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-08-08T03:39:21.157Z
@a3nm "OK, so if I understand correctly, M.Monet's comment means that Holant-based techniques only apply to multigraphs, not graphs."  That is not correct.  The Holant framework is capable of expressing many types of reductions.  Some of those reductions involve parallel edges or self loops and some do not.  A naive way to prove that some problem is hard for simple graphs is to reduce from a problem known to be hard for simple graphs with a reduction that only involves simple graphs.  This approach is definitely possible in the Holant framework.
Tyson Williams
CC BY-SA 4.0
2019-08-08T11:39:35.063Z
@TysonWilliams: Maybe my statement was too strong. My point is that, with the approach from the papers of Cai et al. mentioned in your answer, I don't see how one can show that counting edge covers on graphs is #P-hard. The reason being that their results concern counting problems on 2-3-regular graphs, which when decoded give 3-regular multigraphs, not graphs. So do you agree that the approach proposed in your answer does not work for that reason? Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-08-09T03:36:15.720Z
@a3nm Yes, I agree that the existing Holant dictomoy theorems cannot be directly used to show hardness for the desired problem over simple graphs.  Your question only said "graphs" instead of "simple graphs", so that was my mistake in thinking that you would be satisfied with hardness for multigraphs.
Tyson Williams
CC BY-SA 4.0
2019-08-09T09:19:00.717Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-08-28T12:00:58.020Z
@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 https://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.)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-18T18:13:19.370Z
@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 https://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 :)
M.Monet
CC BY-SA 4.0
2019-05-18T23:47:56.457Z
Ah, yes. Good observation. I am unable to remember right now what results there are for simple graphs.
Tyson Williams
CC BY-SA 3.0
2014-02-28T23:01:35.963Z
2016-12-09T08:37:46.070Z
2016-12-09T08:37:46.070Z
Tyson Williams
<p>An <a href="https://en.wikipedia.org/wiki/Edge_cover">edge cover</a> 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 <a href="https://en.wikipedia.org/wiki/Sharp-P">#P</a>-complete: <a href="http://arxiv.org/pdf/1309.6115v2.pdf">A Simple FPTAS for Counting Edge Covers</a> and <a href="http://world-comp.org/p2013/FCS4082.pdf">Generating Edge Covers of Path Graphs</a>. 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.)</p>

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

<reference-request><graph-algorithms><counting-complexity><proofs>
Complexity of counting the number of edge covers of a graph
Antoine Amarilli 'a3nm'
# Complexity of counting the number of edge covers of a graph

(Asked by: username_0 on 2014-02-27)

An [edge cover](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Sharp-P)-complete: [A Simple FPTAS for Counting Edge Covers](http://arxiv.org/pdf/1309.6115v2.pdf) and [Generating Edge Covers of Path Graphs](http://world-comp.org/p2013/FCS4082.pdf). 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?

**Tags:** reference-request, graph-algorithms, counting-complexity, proofs

---

## 2 answers

### Answer by username_0 on 2017-02-28. Score: 4 | Accepted answer

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](https://arxiv.org/abs/1703.03201). 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](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2005/85262-CS.pdf)*, 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](http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf)*, 2008
* greenhill2000complexity: Catherine Greenhill, *[The complexity of counting colourings and independent sets
  in sparse graphs and hypergraphs](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.467.3100&rep=rep1&type=pdf)*, 2000
* khanna2011queries: Sanjeev Khanna, Sudeepa Roy, Val Tannen, *[Queries with Difference on Probabilistic Databases](https://users.cs.duke.edu/~sudeepa/VLDB11-probdb-difference.pdf)*, 2011.
* vadhan1997complexity: Salil P. Vadhan, *[The Complexity of Counting in Sparse, Regular,
  and Planar Graphs](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.2294&rep=rep1&type=pdf)*, 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.*


---

### Answer by username_1 on 2014-02-28. Score: 11

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](http://en.wikipedia.org/wiki/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](http://cs.nmu.edu/~mkowalcz/research/main.pdf).

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](http://link.springer.com/article/10.1007/s00037-012-0044-6), [preprint](http://pages.cs.wisc.edu/~jyc/papers/interpolation08.pdf)).

(2) [A Dichotomy for $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions](http://link.springer.com/chapter/10.1007/978-3-642-13562-0_30) by Jin-Yi Cai and Michael Kowalczyk.

(3) [Partition functions on $k$-Regular Graphs with $\{0,1\}$-Vertex Assignments and Real Edge Functions](http://www.sciencedirect.com/science/article/pii/S0304397513000091) by Jin-Yi Cai and Michael Kowalczyk.

(4) [Holographic Algorithms](http://epubs.siam.org/doi/abs/10.1137/070682575) by Leslie G. Valiant

(5) [Valiant’s Holant Theorem and matchgate tensors](http://www.sciencedirect.com/science/article/pii/S0304397507004574) by Jin-Yi Cai and Vinay Choudhary

> **Comments:**
> **username_0**: 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!  
> **username_2**: @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 https://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 :)  
> **username_1**: Ah, yes. Good observation. I am unable to remember right now what results there are for simple graphs.  
> **username_0**: OK, so if I understand correctly, @M.Monet's comment means that Holant-based techniques only apply to multigraphs, not graphs. So as far as I can tell, if one wants a proof that counting edge covers on graphs is #P-hard, one should cite bordewich2008path (cf my own answer) -- Tyson's answer in fact does not establish hardness of the right problem.  
> **username_1**: @a3nm "OK, so if I understand correctly, M.Monet's comment means that Holant-based techniques only apply to multigraphs, not graphs."  That is not correct.  The Holant framework is capable of expressing many types of reductions.  Some of those reductions involve parallel edges or self loops and some do not.  A naive way to prove that some problem is hard for simple graphs is to reduce from a problem known to be hard for simple graphs with a reduction that only involves simple graphs.  This approach is definitely possible in the Holant framework.  
> **username_0**: @TysonWilliams: Maybe my statement was too strong. My point is that, with the approach from the papers of Cai et al. mentioned in your answer, I don't see how one can show that counting edge covers on graphs is #P-hard. The reason being that their results concern counting problems on 2-3-regular graphs, which when decoded give 3-regular multigraphs, not graphs. So do you agree that the approach proposed in your answer does not work for that reason? Thanks!  
> **username_1**: @a3nm Yes, I agree that the existing Holant dictomoy theorems cannot be directly used to show hardness for the desired problem over simple graphs.  Your question only said "graphs" instead of "simple graphs", so that was my mistake in thinking that you would be satisfied with hardness for multigraphs.  
> **username_0**: @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.  
> **username_0**: @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 https://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.)  

---

