8

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.

Giorgio Camerani
  • 6,842
  • 1
  • 34
  • 64
  • 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? – 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
  • 1
    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, 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 Sep 14 '10 at 20:26
  • @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 Sep 15 '10 at 02:50
  • @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 Sep 15 '10 at 05:02
  • @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 Sep 15 '10 at 07:24
  • @All: OK, I've edited the question. – Giorgio Camerani Sep 15 '10 at 07:36

2 Answers2

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

Community
  • 1
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • 1
    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 07: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
  • 1
    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
  • @Jukka, Tsuyoshi: See my self-answer below. – Giorgio Camerani Sep 20 '10 at 15:25
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).

Giorgio Camerani
  • 6,842
  • 1
  • 34
  • 64
  • 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
  • @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 Sep 23 '10 at 13:14
  • @Tsuyoshi: OK! ;-) – Giorgio Camerani Sep 23 '10 at 13:48