<ul>
<li><p>Counting edge covers is #P-complete. You can find a proof here <a href="https://dblp.org/rec/conf/soda/BubleyD97" rel="nofollow noreferrer">Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT</a>. See also the <a href="https://cstheory.stackexchange.com/questions/21279/complexity-of-counting-the-number-of-edge-covers-of-a-graph">stack-exchange discussion</a>. One can probably modify the proof to show #P-completeness for minimal edge covers.</p></li>
<li><p>enumerating (minimal) edge covers can be done with polynomial delay as the hypergraph has bounded degree (see <a href="https://epubs.siam.org/doi/10.1137/S009753970240639X" rel="nofollow noreferrer">New Results on Monotone Dualization and Generating Hypergraph Transversals</a>)</p></li>
<li><p>the following <a href="http://dx.doi.org/10.13053/cys-21-3-2244" rel="nofollow noreferrer">Low-Exponential Algorithm for Counting the Number of Edge Covers on Simple Graphs</a> claims an <span class="math-container">$O(1.465575^{(m−n)} × (m + n))$</span> time algorithm. I am wondering whether one cannot do better. </p></li>
</ul>

CC BY-SA 4.0
2018-11-06T14:03:57.560Z
2018-11-06T14:03:57.560Z
M. kanté
<p>A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.</p>

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ol><li> Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial upper bound on their number? Is there any clever algorithm in literature to enumerate them?</li>
  
  <li>Empirically, I'm observing that the number of Minimal Edge Covers seems to be always odd: so far in my experiments I've never met a graph having an even number of them. Is this a theoretically proven fact? If not, has their parity been investigated in literature?</li></ol>
</blockquote>

CC BY-SA 4.0
2018-11-04T18:59:52.937Z
Doesn't $C_4$, the cycle graph on 4 vertices, have two minimal edge covers?
Yonatan N
<cc.complexity-theory><graph-theory><graph-algorithms><counting-complexity>
Counting/Enumerating Minimal Edge Covers
Giorgio Camerani
# Counting/Enumerating Minimal Edge Covers

(Asked by: username_0 on 2018-10-20)

A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.

> **Questions**
>
> 1. Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial upper bound on their number? Is there any clever algorithm in literature to enumerate them?
> 2. Empirically, I'm observing that the number of Minimal Edge Covers seems to be always odd: so far in my experiments I've never met a graph having an even number of them. Is this a theoretically proven fact? If not, has their parity been investigated in literature?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, counting-complexity
> **Comments:**
> **username_1**: Doesn't $C_4$, the cycle graph on 4 vertices, have two minimal edge covers?  

---

## 1 answers

### Answer by username_2 on 2018-11-06. Score: 3

* Counting edge covers is #P-complete. You can find a proof here [Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT](https://dblp.org/rec/conf/soda/BubleyD97). See also the [stack-exchange discussion](https://cstheory.stackexchange.com/questions/21279/complexity-of-counting-the-number-of-edge-covers-of-a-graph). One can probably modify the proof to show #P-completeness for minimal edge covers.
* enumerating (minimal) edge covers can be done with polynomial delay as the hypergraph has bounded degree (see [New Results on Monotone Dualization and Generating Hypergraph Transversals](https://epubs.siam.org/doi/10.1137/S009753970240639X))
* the following [Low-Exponential Algorithm for Counting the Number of Edge Covers on Simple Graphs](http://dx.doi.org/10.13053/cys-21-3-2244) claims an $O(1.465575^{(m−n)} × (m + n))$ time algorithm. I am wondering whether one cannot do better.


---

