8
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ (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? $\endgroup$
    – gphilip
    Sep 14, 2010 at 17:00
  • $\begingroup$ 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. $\endgroup$
    – Daniel Apon
    Sep 14, 2010 at 17:25
  • 1
    $\begingroup$ I think the OP asks whether #Monotone-2SAT (which is #P-complete) can be used to solve K-TRUE-Monotone-2SAT. $\endgroup$
    – Mohammad Al-Turkistany
    Sep 14, 2010 at 17:39
  • $\begingroup$ 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. $\endgroup$
    – András Salamon
    Sep 14, 2010 at 20:23
  • $\begingroup$ In particular, dx.doi.org/10.1007/978-3-642-15155-2_48 appears to consider the MIN-ONES 2-SAT problem in general. $\endgroup$
    – András Salamon
    Sep 14, 2010 at 20:26

2 Answers 2

Reset to default
10
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Giorgio Camerani
    Sep 15, 2010 at 7:42
  • $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Sep 15, 2010 at 10:18
  • 1
    $\begingroup$ 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? $\endgroup$
    – Jukka Suomela
    Sep 15, 2010 at 15:11
  • $\begingroup$ @Jukka: I guess that it will be interesting if there is, but I cannot think of any. $\endgroup$
    – Tsuyoshi Ito
    Sep 15, 2010 at 15:29
  • $\begingroup$ @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$? $\endgroup$
    – Giorgio Camerani
    Sep 16, 2010 at 10:34
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.