# Monotone-2SAT and Vertex Cover

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.

• (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 Sep 14 '10 at 17:00
• 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 Sep 14 '10 at 17:25
• I think the OP asks whether #Monotone-2SAT (which is #P-complete) can be used to solve K-TRUE-Monotone-2SAT. – Mohammad Al-Turkistany Sep 14 '10 at 17:39
• 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 Sep 14 '10 at 20:23
• In particular, 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 Sep 14 '10 at 20:26

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

• 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 Sep 15 '10 at 7:42
• @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 Sep 15 '10 at 10:18
• 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 Sep 15 '10 at 15:11
• @Jukka: I guess that it will be interesting if there is, but I cannot think of any. – Tsuyoshi Ito Sep 15 '10 at 15:29
• @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 Sep 16 '10 at 10:34

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

• 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 Sep 22 '10 at 12:04
• @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 Sep 22 '10 at 12:43
• ...so I agree the question is still open, but I think we are closer to the answer. – Giorgio Camerani Sep 22 '10 at 12:44
• 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 Sep 22 '10 at 13:11
• Tsuyoshi, if you want I can give you the paper. I tried again and it works here. – Giorgio Camerani Sep 22 '10 at 13:47