Max 2-sat and clause size

Question

I've seen that Max 2-Sat is NP-complete, are there instances in which every clause has exactly $2$ variables which are $NP$-complete? Or do all such instance need to contain a clause of exactly 1 variable?

Answer 1

First of all, note that no instance itself is NP-complete. I will reformulate your question in a way that makes sense, hopefully capturing what you meant to ask.

Let Strict Max 2-SAT be the problem whose instances are those in Max 2-SAT where all clauses have 2 variables. The question is whether Strict Max 2-SAT is NP-hard.

We can reduce Max 2-SAT to Strict Max 2-SAT, which means that Max 2-SAT's NP-hardness implies Strict Max 2-SAT is also NP-hard, as follows. Let $x$ be an instance of Max 2-SAT. We will replace each clause of $x$ consisting of one variable with two clauses consisting of two variables; call this new instance $y$, which is an instance of Strict Max 2-SAT. This replacement will be such that a maximum assignment to $x$ corresponds in a simple way to a maximum assignment to $y$. Therefore solving $y$ gives a solution to $x$, completing the reduction.

Consider a clause of $x$ that has just one variable, say $(u)$ (if the clause consists of a negated variable then let $u$ be the negated variable). We introduce a new variable, say $v$, and replace $(u)$ by $(u \lor v) \land (u \lor \neg v)$. Note that when $u$ is true then both clauses in the replacement can be made true but when $u$ is false, at most one clause in the replacement can be made true. So fixing the value of $u$, the replacement's maximum satisfiability is one greater than the original clause's satisfiability. Therefore if $n$ is the number of single-variable clauses in $x$, $y$'s maximum satisfiability is $x$'s maximum satisfiability $+ n$.

Answer 2

If a single 2-SAT clause contains the same variable twice, then either both literals are equal (in which there is only one way to set the variable, which reduces the 2-SAT formula), or one literal is the negation of the other, in which case any way you set the variable will satisfy that clause and thus that clause can be deleted. So yes, in general, you can assume that in a general Max 2-SAT problem, that every clause involves two different variables in some form (negated or not, although there may be multiple clauses that involve a certain variable or its negation).