<p>In any graph, the parity of the number of vertex covers is equal to the parity of the number of edge covers.</p>

<p>To see why, check <a href="https://cstheory.stackexchange.com/a/14911/947">this answer</a> and observe how the parity of $|C|$ is equal to the parity of $\Delta_{|V|} = O_{|V|} - E_{|V|}$, which is in turn equal to the parity of $O_{|V|} + E_{|V|}$, which is the number of edge covers.</p>

<p>Computing the parity of the number of vertex covers is $\oplus$P-hard: therefore computing the parity of the number of edge covers is $\oplus$P-hard as well.</p>

<p>At least the second half of the question has been settled.</p>

CC BY-SA 3.0
2013-06-09T07:38:23.763Z
2013-06-10T21:17:56.490Z
2017-04-13T12:32:28.080Z
Giorgio Camerani
<p>Your problem is probably #P-complete, though I haven't been able to find it in the literature.</p>

<p>Another way of stating your problem is "#3-regular-edge-cover". Given a formula, construct a graph in which each clause corresponds to a vertex and each variable corresponds to an edge. Since the formula is a 3CNF, the graph is 3-regular (or has maximum degree 3, depending on the definition). Furthermore, the graph is simple. A satisfying assignment is the same as an edge cover.</p>

<p>Here are a few related problems:</p>

<ul>
<li><a href="http://rangevoting.org/HuntMRS98.pdf" rel="nofollow">#1-Ex3MonoSat is #P-complete</a>. This is the same as your problem, only a satisfying solution has to satisfy exactly one variable in each clause.</li>
<li><a href="http://link.springer.com/chapter/10.1007/11750321_34" rel="nofollow">Counting the number of <em>vertex</em> covers in 3-regular planar graphs is #P-complete</a>.</li>
<li>There is an <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.1199&amp;rep=rep1&amp;type=pdf" rel="nofollow">FPRAS for #3-regular-edge cover</a>. This suggests that the authors believe that the problem is hard.</li>
</ul>

CC BY-SA 3.0
2013-04-06T15:24:40.120Z
I do not see how his #restricted-Monotone3CNF is the same thing as the #1-Ex3MonoSAT. Nevermind, the fact that the later problem wants exactly one literal to be satisfied. He wants Monotone 3 CNF formulas such that each variable appears in exactly two clauses and each clause shares at most 1 variable. There is no such restriction in #1-Ex3MonoSAT.
Tayfun Pay
CC BY-SA 3.0
2013-04-17T01:31:17.183Z
I tried to convey this difference using the word "only", but I agree that this is not the best possible choice of words.
Yuval Filmus
CC BY-SA 3.0
2013-04-06T05:33:51.043Z
2013-04-06T05:33:51.043Z
Yuval Filmus
<p>Consider a Monotone 3CNF formula having both the following additional restrictions:</p>

<ul>
<li>Every variable appears in exactly $2$ clauses.</li>
<li>Given any $2$ clauses, they share at most $1$ variable.</li>
</ul>

<p>I would like to know how hard is counting the satisfying assignments of such a formula.</p>

<hr>

<p><strong>Update 06/04/2013 12:55</strong></p>

<p>I would also like to know how hard is determining the parity of the number of satisfying assignments.</p>

<hr>

<p><strong>Update 11/04/2013 22:40</strong></p>

<p>What if, in addition to the restrictions described above, we also introduce both the following restrictions:</p>

<ul>
<li>The formula is planar.</li>
<li>The formula is bipartite.</li>
</ul>

<hr>

<p><strong>Update 16/04/2013 23:00</strong></p>

<p>Each satisfying assignment corresponds to an edge cover of a $3$-regular graph. After extensive search, the only relevant paper I was able to find on counting edge covers is the (3rd) one already mentioned in Yuval's answer. At the beginning of such paper, the authors say <em>"We <strong>initiate</strong> the study of sampling (and the related question of counting) of all edge covers of a graph"</em>. I'm very surprised that this problem has received so few attention (compared to counting vertex covers, which is widely studied and much better understood, for several graph classes). We do not know whether counting edge covers is $\#P$-hard. We do not know whether determining the parity of the number of edge covers is $\oplus P$-hard, either.</p>

<hr>

<p><strong>Update 09/06/2013 07:38</strong></p>

<p>Determining the parity of the number of edge covers is $\oplus P$-hard, check answer below.</p>

CC BY-SA 3.0
2013-04-05T21:48:25.650Z
I think it is more interesting if you restrict it to literals instead of variables.
Tayfun Pay
CC BY-SA 3.0
2013-04-05T23:22:25.870Z
@Tayfun Since the formula is monotone, these are equivalent.
Tyson Williams
CC BY-SA 3.0
2013-04-06T00:54:04.707Z
@TysonWilliams Thanks I should not comment on things when I am sleepy.
Tayfun Pay
CC BY-SA 3.0
2013-04-17T01:30:26.993Z
@Giorgio Using the existing reductions, it might not be hard to prove that the problem is $\#P$-hard. You should try reading the relevant parts of the two other papers I quote.
Yuval Filmus
CC BY-SA 3.0
2013-08-31T06:59:16.437Z
@Downvoter: Why?
Giorgio Camerani
CC BY-SA 3.0
2013-08-31T17:33:50.813Z
@Downvoter: Moreover you are one of those who upvoted in the first place. Bizarre.
Giorgio Camerani
<cc.complexity-theory><sat><counting-complexity>
Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)
Giorgio Camerani
# Restricted Monotone 3CNF formula: counting satisfying assignments (both modulo $2^n$ and modulo $2$)

(Asked by: username_0 on 2013-04-05)

Consider a Monotone 3CNF formula having both the following additional restrictions:

* Every variable appears in exactly $2$ clauses.
* Given any $2$ clauses, they share at most $1$ variable.

I would like to know how hard is counting the satisfying assignments of such a formula.

---

**Update 06/04/2013 12:55**

I would also like to know how hard is determining the parity of the number of satisfying assignments.

---

**Update 11/04/2013 22:40**

What if, in addition to the restrictions described above, we also introduce both the following restrictions:

* The formula is planar.
* The formula is bipartite.

---

**Update 16/04/2013 23:00**

Each satisfying assignment corresponds to an edge cover of a $3$-regular graph. After extensive search, the only relevant paper I was able to find on counting edge covers is the (3rd) one already mentioned in Yuval's answer. At the beginning of such paper, the authors say *"We **initiate** the study of sampling (and the related question of counting) of all edge covers of a graph"*. I'm very surprised that this problem has received so few attention (compared to counting vertex covers, which is widely studied and much better understood, for several graph classes). We do not know whether counting edge covers is $\#P$-hard. We do not know whether determining the parity of the number of edge covers is $\oplus P$-hard, either.

---

**Update 09/06/2013 07:38**

Determining the parity of the number of edge covers is $\oplus P$-hard, check answer below.

**Tags:** cc.complexity-theory, sat, counting-complexity

> **Comments:**
> **username_1**: I think it is more interesting if you restrict it to literals instead of variables.  
> **username_2**: @Tayfun Since the formula is monotone, these are equivalent.  
> **username_1**: @TysonWilliams Thanks I should not comment on things when I am sleepy.  
> **username_3**: @Giorgio Using the existing reductions, it might not be hard to prove that the problem is $\#P$-hard. You should try reading the relevant parts of the two other papers I quote.  
> **username_0**: @Downvoter: Why?  
> **username_0**: @Downvoter: Moreover you are one of those who upvoted in the first place. Bizarre.  

---

## 2 answers

### Answer by username_0 on 2013-06-09. Score: 6

In any graph, the parity of the number of vertex covers is equal to the parity of the number of edge covers.

To see why, check [this answer](https://cstheory.stackexchange.com/a/14911/947) and observe how the parity of $|C|$ is equal to the parity of $\Delta\_{|V|} = O\_{|V|} - E\_{|V|}$, which is in turn equal to the parity of $O\_{|V|} + E\_{|V|}$, which is the number of edge covers.

Computing the parity of the number of vertex covers is $\oplus$P-hard: therefore computing the parity of the number of edge covers is $\oplus$P-hard as well.

At least the second half of the question has been settled.


---

### Answer by username_3 on 2013-04-06. Score: 3

Your problem is probably #P-complete, though I haven't been able to find it in the literature.

Another way of stating your problem is "#3-regular-edge-cover". Given a formula, construct a graph in which each clause corresponds to a vertex and each variable corresponds to an edge. Since the formula is a 3CNF, the graph is 3-regular (or has maximum degree 3, depending on the definition). Furthermore, the graph is simple. A satisfying assignment is the same as an edge cover.

Here are a few related problems:

* [#1-Ex3MonoSat is #P-complete](http://rangevoting.org/HuntMRS98.pdf). This is the same as your problem, only a satisfying solution has to satisfy exactly one variable in each clause.
* [Counting the number of *vertex* covers in 3-regular planar graphs is #P-complete](http://link.springer.com/chapter/10.1007/11750321_34).
* There is an [FPRAS for #3-regular-edge cover](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.182.1199&rep=rep1&type=pdf). This suggests that the authors believe that the problem is hard.

> **Comments:**
> **username_1**: I do not see how his #restricted-Monotone3CNF is the same thing as the #1-Ex3MonoSAT. Nevermind, the fact that the later problem wants exactly one literal to be satisfied. He wants Monotone 3 CNF formulas such that each variable appears in exactly two clauses and each clause shares at most 1 variable. There is no such restriction in #1-Ex3MonoSAT.  
> **username_3**: I tried to convey this difference using the word "only", but I agree that this is not the best possible choice of words.  

---

