4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.