9
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ I think it is more interesting if you restrict it to literals instead of variables. $\endgroup$
    – Tayfun Pay
    Commented Apr 5, 2013 at 21:48
  • 3
    $\begingroup$ @Tayfun Since the formula is monotone, these are equivalent. $\endgroup$
    – Tyson Williams
    Commented Apr 5, 2013 at 23:22
  • $\begingroup$ @TysonWilliams Thanks I should not comment on things when I am sleepy. $\endgroup$
    – Tayfun Pay
    Commented Apr 6, 2013 at 0:54
  • 2
    $\begingroup$ @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. $\endgroup$
    – Yuval Filmus
    Commented Apr 17, 2013 at 1:30
  • $\begingroup$ @Downvoter: Why? $\endgroup$
    – Giorgio Camerani
    Commented Aug 31, 2013 at 6:59

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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:

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tayfun Pay
    Commented Apr 6, 2013 at 15:24
  • 2
    $\begingroup$ I tried to convey this difference using the word "only", but I agree that this is not the best possible choice of words. $\endgroup$
    – Yuval Filmus
    Commented Apr 17, 2013 at 1:31

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.