Maximum 2-Satisfiability

Input

Set $U$ of variables, collection $C$ of clauses over $U$ such that each clause $c \in C$ has $|c| = 2$, positive integer $K \leq |C|$

Question

Is there a truth assignment for $U$ that simultaneously satisfies at least $K$ of the clauses in $C$?

Classes

• NP-complete

Comments

Solvable in polynomial time if $K = |C|$ (e.g. see (Even et al., 1976)).

Proofs

NP-complete

Transformation from 3-Satisfiability (Garey et al., 1976).

Reducible from

• 3-Satisfiability

Reducible to

• Max Cut

References

• Even, S., Itai, A., & Shamir, A. (1976). On the Complexity of Timetable and Multicommodity Flow Problems. SIAM Journal on Computing, 5(4), 691–703. https://doi.org/10.1137/0205048
• Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10.1016/0304-3975(76)90059-1