2
$\begingroup$

Weighted 2SAT asks if it is possible to satisfy the formula with at most $k$ variables set as positive/negative. Trivially, every instance must be in 2CNF. It is known to be $\mathsf{NP}$-complete.

We have following additional restriction: each variable appears twice as positive and once as negative or vice versa.

Example of instance:

$(x\lor y)\land(x\lor z)\land(\overline x\lor t)\land(\overline y\lor z)\land(\overline y\lor \overline t)\land(\overline z\lor \overline t)$

Is this weighted 2SAT variant $\mathsf{NP}$-complete?

Of course, if vertex cover where each vertex has only 2 edges is $\mathsf{NP}$-hard, this also must be $\mathsf{NP}$-hard. So, if such result is known, then it also can be an answer. Ah, well, this does not help.

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you mean " each variable appears at most twice as positive and at most once as negative or vice versa"? If yes, can you edit the question? If not, I don't how this is the same as vertex cover; can you edit the question to elaborate? $\endgroup$
    – D.W. ♦
    Commented Aug 21, 2017 at 6:30
  • $\begingroup$ It's trivial to find the minimum vertex cover for a graph where each vertex has at most 2 edges: it's either a line or a cycle, and it's easy to find the minimum vertex cover for those kinds of graphs. So you're not going to prove a hardness result in that way. $\endgroup$
    – D.W. ♦
    Commented Aug 21, 2017 at 6:33
  • $\begingroup$ @D.W. In fact this is not a vertex cover because formula is not monotone. I don't know if problem becomes easier if we allow variables to appear only twice (in case of 3SAT it makes problem easier). $\endgroup$
    – rus9384
    Commented Aug 21, 2017 at 7:25

1 Answer 1

Reset to default
5
$\begingroup$

You can express the predicate "$x = y$" using one occurrence of each polarity: $$ (x \lor \lnot y) \land (\lnot x \lor y). $$ Consider now an instance of weighted 2SAT, in which each variable appears at most $M$ times. Duplicate each variable $M$ times, and enforce that all copies are the same using the gadget above. Replace each occurrence of each variable by a distinct copy of the variable. If the original instance asks for an assignment with at most $k$ positive variables, ask for at most $Mk$ positive variables. We obtain an instance of your problem which is equivalent to the original problem.

This shows that your problem is also NP-complete.

Improve this answer
$\endgroup$

Your Answer

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

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