2
$\begingroup$

The Max-2SAT problem asks if at least k clauses of a 2CNF formula can be satisfied.

The Max-2SAT(at-most-3) problem is the restriction in which every variable occurs in at most 3 clauses (counting positive and negative occurrences together). It is known that this problem is APX-hard, the reference being this book. However, I can't access the book, so I can't look at the details.

The Max-2SAT(exactly-3) problem is the restriction in which every variable occurs in exactly 3 clauses, i.e. no variable occurs only twice. From this paper, I believe the problem is NP-hard. But I don't know if it's also APX-hard. Is it? Does it follows from the "at-most-3" case? If not, I'd like to know how many of the n variables occur only twice, and not three times.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Have you tried coming up with an algorithm and/or a reduction? $\endgroup$
    – Raphael
    Commented Sep 20, 2016 at 19:38
  • $\begingroup$ I did try to reduce the "at-most-3" case to the "exactly-3" case, by attempting to add 1 occurrence for the 2-occurrence variables and incorporating new dummy variables. That does not behave too well however. Other ideas are welcome. Also, if anyone knows about the cited APX-hardness reduction, I'd be happy to see it. $\endgroup$
    – Manuel Lafond
    Commented Sep 21, 2016 at 19:47

0

Reset to default

Your Answer

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