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.
Balanced Max-2-SAT NP-Hardness
np hardness;sat;max2sat
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.