# Is this case of weighted 2SAT NP-complete?

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.

• 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? – D.W. Aug 21 '17 at 6:30
• 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. – D.W. Aug 21 '17 at 6:33
• @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). – rus9384 Aug 21 '17 at 7:25

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.