Pergunta

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.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top