Questo caso di NP-completo 2SAT ponderato?

Question

2Sat ponderato chiede se è possibile soddisfare la formula con le variabili di $ k $ impostate come positive/negative. Brivialmente, ogni istanza deve essere in 2CNF. È noto per essere $ mathsf {np} $-completo.

Abbiamo seguito ulteriori restrizioni: ogni variabile appare due volte più positiva e una volta negativa o viceversa.

Esempio di istanza:

$ (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) $

Questa variante 2sat ponderata è $ mathsf {np} $-completa?

Naturalmente, se la copertura del vertice in cui ogni vertice ha solo 2 bordi è $ mathsf {np} $-hard, questo deve anche essere $ mathsf {np} $-hard. Quindi, se tale risultato è noto, allora può anche essere una risposta. Ah, beh, questo non aiuta.