<p>The name “#Monotone-2SAT” usually refers to the problem of counting the satisfying assignments of a given monotone 2CNF formula, without a restriction on the number of variables set to true.  The stated “Monotone 2SAT” problem, or the Vertex Cover problem as is usually called, is <em>not</em> the decision version of #Monotone-2SAT because of the additional restriction on the number of variables set to true.  (This is certainly unfortunate.)  Therefore, Vertex Cover (or “Monotone 2SAT”) is not reducible to #Monotone-2SAT in the same way as 3SAT is reducible to #3SAT.</p>

<p>Note that Vertex Cover is clearly in NP and that #Monotone-2SAT is known to be #P-complete (see <a href="https://cstheory.stackexchange.com/questions/1247/reducing-sat-to-monotone-2sat/1251#1251">my answer to your previous question</a> for the reference) and hence NP-hard.  Therefore, Vertex Cover <em>is</em> reducible to #Monotone-2SAT.  (Note that this does not require the fact that Vertex Cover is NP-complete.)  To construct an actual reduction, you can simply composing several reductions as always.  There may be a simpler reduction than this, but I do not expect that seeking for a simpler reduction gives much insight into either problem.</p>

CC BY-SA 2.5
2010-09-15T07:42:33.597Z
Hello Tsuyoshi, my question was imprecise: I've just edited it to clarify. I know that I can solve k-True-Monotone-2SAT by converting it to Vertex Cover, then Vertex Cover to SAT, then SAT to #SAT, then #SAT to Permanent, then Permanent to 01-Permanent, then 01-Permanent to #Monotone-2SAT. But I'm looking for a simpler reduction: such simpler reduction is the core of my question.
Giorgio Camerani
CC BY-SA 2.5
2010-09-15T10:18:20.647Z
@Walter: In that case, as I wrote in my answer, I do not expect that finding a simpler reduction leads to better understanding of the problems.  I am happy to be proven wrong, though.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-15T15:11:06.760Z
Do we have *any* natural examples of graph problems with the following property: if you can count the number of feasible solutions, then it is fairly easy (but not completely trivial) to find a minimum-size solution?
Jukka Suomela
CC BY-SA 2.5
2010-09-15T15:29:39.643Z
@Jukka: I guess that it will be interesting if there is, but I cannot think of any.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-16T10:34:50.450Z
@Jukka: Your question is exactly what I'd like to know. Given an oracle that tells us the number of vertex covers of a graph $G$, how could we use it to easily determine the number of k-vertex covers of $G$?
Giorgio Camerani
CC BY-SA 2.5
2010-09-20T15:25:36.933Z
@Jukka, Tsuyoshi: See my self-answer below.
Giorgio Camerani
CC BY-SA 2.5
2010-09-15T00:09:34.380Z
2010-09-15T00:09:34.380Z
2017-04-13T12:32:28.117Z
Tsuyoshi Ito
<p>I've found this very interesting thesis by Salil Vadhan: <a href="http://www.hcs.harvard.edu/thesis/repo/31/2/ugthesis.pdf" rel="nofollow">http://www.hcs.harvard.edu/thesis/repo/31/2/ugthesis.pdf</a>. The answer to my question seems to be in the proof of statement 9 of Theorem 5.2 (on page 36).</p>

CC BY-SA 2.5
2010-09-22T12:04:18.937Z
I cannot access the paper you linked to right now by internal server error.  (The server seems to have gone down after I had a glance at the statement in the paper.)  However, if I remember correctly, the statement you mentioned is a reduction from a counting problem to a counting problem, so I do not see how it answers your revised question (revision 2).  One of the problems is about counting the minimum solutions in some sense, but it is still a counting problem.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T12:43:40.377Z
@Tsuyoshi: I've tried to reach the paper, it works. The paper, among other things, shows how it is possible to count the number of minimum vertex covers of a graph $G$ by counting the number of vertex covers of a graph $G'$ constructed from $G$. To show that, the author goes through several intermediate reductions (namely, from statements 5 to 8 in Theorem 5.2). Actually, the very question to which the paper seems to answer is the one posed by Jukka in its comment above. I feel that being able to solve #Min-Ones-Monotone-2SAT should give us the ability to solve also Min-Ones-Monotone-2SAT...
Giorgio Camerani
CC BY-SA 2.5
2010-09-22T12:44:07.973Z
...so I agree the question is still open, but I think we are closer to the answer.
Giorgio Camerani
CC BY-SA 2.5
2010-09-22T13:11:18.293Z
I still cannot reach the paper (this time the server says Service Temporarily Unavailable).  Depending on the definition of #Min-Ones-Monotone-2SAT in the paper, I may not share your feeling that “being able to solve #Min-Ones-Monotone-2SAT should give us the ability to solve also Min-Ones-Monotone-2SAT.”  But I am happy if you are right.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-22T13:47:54.327Z
Tsuyoshi, if you want I can give you the paper. I tried again and it works here.
Giorgio Camerani
CC BY-SA 2.5
2010-09-23T13:14:59.143Z
@Walter: Thanks, but I am afraid that I will not have time to study the paper.  Anyway if the paper gives you something you want, I have no complaint about it.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-23T13:48:51.853Z
@Tsuyoshi: OK! ;-)
Giorgio Camerani
CC BY-SA 2.5
2010-09-20T12:53:51.033Z
2010-09-20T12:53:51.033Z
Giorgio Camerani
<p>The following decision problem is called k-True-Monotone-2SAT:</p>

<blockquote>
  <p>Given a 2-CNF boolean formula $F$ that does not contain any negated variables
  and given a positive integer $k$, can $F$ be satisfied by setting $k$ or fewer
  variables to true?</p>
</blockquote>

<p>It is NP-complete: it's easy to see a straightforward reduction from Vertex Cover to it (i.e. can we cover all the edges with $k$ or fewer nodes?).</p>

<p>The following decision problem is called Monotone-2SAT:</p>

<blockquote>
  <p>Given a 2-CNF boolean formula $F$ that does not contain any negated variables, is it satisfiable?</p>
</blockquote>

<p>As a decision problem, Monotone-2SAT is trivial. The answer is always YES: just set every variable to true.</p>

<p>But consider its counting version, called #Monotone-2SAT:</p>

<blockquote>
  <p>Given a 2-CNF boolean formula $F$ that does not contain any negated variables, how many satisfying assignments $F$ has?</p>
</blockquote>

<p>Surprisingly, #Monotone-2SAT is #P-complete.</p>

<p>Now here is the question. Suppose we have an oracle for #Monotone-2SAT, which returns the exact solution count of a Monotone-2SAT formula: how such solution count can be used to solve k-True-Monotone-2SAT?</p>

<p>I'm asking this because I do not immediately see how the solution count may give information on how many solutions have k or less literals set to true and how many don't.</p>

CC BY-SA 2.5
2010-09-14T17:00:29.173Z
(1) In what sense does the reference that you mention show that the Monotone-2SAT problem is _equivalent_ to the Vertex Cover problem? In the sense that both are NP-complete?  (2) What exactly does the oracle for #Monotone-2SAT return? To me it looks like it returns the number of different satisfying assignments of F that set k or fewer variables to true. If this is the case, can't we look at this number and say YES or NO for the Monotone-2SAT problem depending on whether the number is positive or zero, respectively?
gphilip
CC BY-SA 2.5
2010-09-14T17:25:25.783Z
Along with gphilip's comment, you might want to clarify what you're actually asking in your final sentence... Looking at what you've written, I would say that the solution count that the oracle to #Monotone-2SAT returns is exactly defined as the number of solutions that have k or less literals set to true that also cause the Boolean formula F to evaluate to true.
Daniel Apon
CC BY-SA 2.5
2010-09-14T17:39:28.590Z
I think the OP asks whether #Monotone-2SAT (which is #P-complete) can be used to solve K-TRUE-Monotone-2SAT.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-14T20:23:35.007Z
When trying to minimize the number of 1's in an assignment, the problem is MIN-ONES.  #2-MONOTONE-SAT is establishing the number of satisfying assignments, which is not the same thing.
András Salamon
CC BY-SA 2.5
2010-09-14T20:26:00.683Z
In particular, http://dx.doi.org/10.1007/978-3-642-15155-2_48 appears to consider the MIN-ONES 2-SAT problem in general.
András Salamon
CC BY-SA 2.5
2010-09-15T02:50:03.790Z
@gphilip: As for your question (1), the Monotone 2SAT problem in the question is really the same problem as the Vertex Cover problem if you consider a monotone 2CNF formula as a graph with vertices representing variables and edges representing clauses.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-15T05:02:27.083Z
@Tsuyoshi: Thank you. Also, as per the reference that  András mentions, even the more general Min-Ones 2-SAT problem is equivalent to Vertex Cover.
gphilip
CC BY-SA 2.5
2010-09-15T07:24:54.313Z
@All: Here I am. Sorry, my question was imprecise. The source of confusion is that the article I've mentioned calls that problem Monotone-2SAT, while it should call it k-True-Monotone-2SAT (as pointed out by turkistany). I'm going to edit my question to clarify it.
Giorgio Camerani
CC BY-SA 2.5
2010-09-15T07:36:29.200Z
@All: OK, I've edited the question.
Giorgio Camerani
<cc.complexity-theory><ds.algorithms><sat>
Monotone-2SAT and Vertex Cover
Giorgio Camerani
# Monotone-2SAT and Vertex Cover

(Asked by: username_0 on 2010-09-14)

The following decision problem is called k-True-Monotone-2SAT:

> Given a 2-CNF boolean formula $F$ that does not contain any negated variables
> and given a positive integer $k$, can $F$ be satisfied by setting $k$ or fewer
> variables to true?

It is NP-complete: it's easy to see a straightforward reduction from Vertex Cover to it (i.e. can we cover all the edges with $k$ or fewer nodes?).

The following decision problem is called Monotone-2SAT:

> Given a 2-CNF boolean formula $F$ that does not contain any negated variables, is it satisfiable?

As a decision problem, Monotone-2SAT is trivial. The answer is always YES: just set every variable to true.

But consider its counting version, called #Monotone-2SAT:

> Given a 2-CNF boolean formula $F$ that does not contain any negated variables, how many satisfying assignments $F$ has?

Surprisingly, #Monotone-2SAT is #P-complete.

Now here is the question. Suppose we have an oracle for #Monotone-2SAT, which returns the exact solution count of a Monotone-2SAT formula: how such solution count can be used to solve k-True-Monotone-2SAT?

I'm asking this because I do not immediately see how the solution count may give information on how many solutions have k or less literals set to true and how many don't.

**Tags:** cc.complexity-theory, ds.algorithms, sat
> **Comments:**
> **username_1**: (1) In what sense does the reference that you mention show that the Monotone-2SAT problem is _equivalent_ to the Vertex Cover problem? In the sense that both are NP-complete?  (2) What exactly does the oracle for #Monotone-2SAT return? To me it looks like it returns the number of different satisfying assignments of F that set k or fewer variables to true. If this is the case, can't we look at this number and say YES or NO for the Monotone-2SAT problem depending on whether the number is positive or zero, respectively?  
> **username_2**: Along with gphilip's comment, you might want to clarify what you're actually asking in your final sentence... Looking at what you've written, I would say that the solution count that the oracle to #Monotone-2SAT returns is exactly defined as the number of solutions that have k or less literals set to true that also cause the Boolean formula F to evaluate to true.  
> **username_3**: I think the OP asks whether #Monotone-2SAT (which is #P-complete) can be used to solve K-TRUE-Monotone-2SAT.  
> **username_4**: When trying to minimize the number of 1's in an assignment, the problem is MIN-ONES.  #2-MONOTONE-SAT is establishing the number of satisfying assignments, which is not the same thing.  
> **username_4**: In particular, http://dx.doi.org/10.1007/978-3-642-15155-2_48 appears to consider the MIN-ONES 2-SAT problem in general.  
> **username_5**: @gphilip: As for your question (1), the Monotone 2SAT problem in the question is really the same problem as the Vertex Cover problem if you consider a monotone 2CNF formula as a graph with vertices representing variables and edges representing clauses.  
> **username_1**: @Tsuyoshi: Thank you. Also, as per the reference that  András mentions, even the more general Min-Ones 2-SAT problem is equivalent to Vertex Cover.  
> **username_0**: @All: Here I am. Sorry, my question was imprecise. The source of confusion is that the article I've mentioned calls that problem Monotone-2SAT, while it should call it k-True-Monotone-2SAT (as pointed out by turkistany). I'm going to edit my question to clarify it.  
> **username_0**: @All: OK, I've edited the question.  

---

## 2 answers

### Answer by username_5 on 2010-09-15. Score: 10

The name “#Monotone-2SAT” usually refers to the problem of counting the satisfying assignments of a given monotone 2CNF formula, without a restriction on the number of variables set to true. The stated “Monotone 2SAT” problem, or the Vertex Cover problem as is usually called, is *not* the decision version of #Monotone-2SAT because of the additional restriction on the number of variables set to true. (This is certainly unfortunate.) Therefore, Vertex Cover (or “Monotone 2SAT”) is not reducible to #Monotone-2SAT in the same way as 3SAT is reducible to #3SAT.

Note that Vertex Cover is clearly in NP and that #Monotone-2SAT is known to be #P-complete (see [my answer to your previous question](https://cstheory.stackexchange.com/questions/1247/reducing-sat-to-monotone-2sat/1251#1251) for the reference) and hence NP-hard. Therefore, Vertex Cover *is* reducible to #Monotone-2SAT. (Note that this does not require the fact that Vertex Cover is NP-complete.) To construct an actual reduction, you can simply composing several reductions as always. There may be a simpler reduction than this, but I do not expect that seeking for a simpler reduction gives much insight into either problem.

> **Comments:**
> **username_0**: Hello Tsuyoshi, my question was imprecise: I've just edited it to clarify. I know that I can solve k-True-Monotone-2SAT by converting it to Vertex Cover, then Vertex Cover to SAT, then SAT to #SAT, then #SAT to Permanent, then Permanent to 01-Permanent, then 01-Permanent to #Monotone-2SAT. But I'm looking for a simpler reduction: such simpler reduction is the core of my question.  
> **username_5**: @Walter: In that case, as I wrote in my answer, I do not expect that finding a simpler reduction leads to better understanding of the problems.  I am happy to be proven wrong, though.  
> **username_6**: Do we have *any* natural examples of graph problems with the following property: if you can count the number of feasible solutions, then it is fairly easy (but not completely trivial) to find a minimum-size solution?  
> **username_5**: @Jukka: I guess that it will be interesting if there is, but I cannot think of any.  
> **username_0**: @Jukka: Your question is exactly what I'd like to know. Given an oracle that tells us the number of vertex covers of a graph $G$, how could we use it to easily determine the number of k-vertex covers of $G$?  
> **username_0**: @Jukka, Tsuyoshi: See my self-answer below.  

---

### Answer by username_0 on 2010-09-20. Score: 1

I've found this very interesting thesis by Salil Vadhan: <http://www.hcs.harvard.edu/thesis/repo/31/2/ugthesis.pdf>. The answer to my question seems to be in the proof of statement 9 of Theorem 5.2 (on page 36).

> **Comments:**
> **username_5**: I cannot access the paper you linked to right now by internal server error.  (The server seems to have gone down after I had a glance at the statement in the paper.)  However, if I remember correctly, the statement you mentioned is a reduction from a counting problem to a counting problem, so I do not see how it answers your revised question (revision 2).  One of the problems is about counting the minimum solutions in some sense, but it is still a counting problem.  
> **username_0**: @Tsuyoshi: I've tried to reach the paper, it works. The paper, among other things, shows how it is possible to count the number of minimum vertex covers of a graph $G$ by counting the number of vertex covers of a graph $G'$ constructed from $G$. To show that, the author goes through several intermediate reductions (namely, from statements 5 to 8 in Theorem 5.2). Actually, the very question to which the paper seems to answer is the one posed by Jukka in its comment above. I feel that being able to solve #Min-Ones-Monotone-2SAT should give us the ability to solve also Min-Ones-Monotone-2SAT...  
> **username_0**: ...so I agree the question is still open, but I think we are closer to the answer.  
> **username_5**: I still cannot reach the paper (this time the server says Service Temporarily Unavailable).  Depending on the definition of #Min-Ones-Monotone-2SAT in the paper, I may not share your feeling that “being able to solve #Min-Ones-Monotone-2SAT should give us the ability to solve also Min-Ones-Monotone-2SAT.”  But I am happy if you are right.  
> **username_0**: Tsuyoshi, if you want I can give you the paper. I tried again and it works here.  
> **username_5**: @Walter: Thanks, but I am afraid that I will not have time to study the paper.  Anyway if the paper gives you something you want, I have no complaint about it.  
> **username_0**: @Tsuyoshi: OK! ;-)  

---

