# Balanced Max-2-SAT NP-Hardness

The Balanced Max-2-SAT is a special case of Max-2-SAT (each clause is a disjunction of exactly 2 literals) in which for every variable $x$, there is a $k$ such that $x$ appears positive exactly $k$ times in the clauses, and exactly $k$ times negative in the clauses.

I'm looking for a published proof of NP-Hardness for this problem, for references.

It is implied NP-Hard by [this paper], but I can't find the original NP-Hardness proof.

Is it a consequence of the hardness of Max-2-SAT ?

Also as a bonus, Balanced Max-2-SAT($k$) is the subcase in which every variable appears exactly $k$ times positive, exactly $k$ times negative. Is there some known $k$ for which NP-Hardness is published? I know that Balanced Max-3-SAT(2) is hard, but found nothing for the $2$ case.

## 1 Answer

I think it is possible to reduce Max Cut to this problem: given a graph $G(V,E)$, make a variable for each vertex, and for each edge $(u,v)\in E$ make the two clauses $(x_u\lor x_v)$ and $(\neg x_u\lor\neg x_v)$. In the resulting instance, $x_u$ appears $d(x_u)$ times positive and the same number of times negative. Since Max Cut is still NP-hard on regular graphs, this proves that the version for which $k$ is the same for all variables is also hard.

• Marvelous, that seems to work! – Manuel Lafond Mar 8 '16 at 18:27