<p>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.</p>

CC BY-SA 3.0
2016-03-08T18:27:54.687Z
Marvelous, that seems to work!
Manuel Lafond
CC BY-SA 3.0
2016-03-08T13:07:22.457Z
2016-03-08T13:07:22.457Z
Michael Lampis
<p>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. </p>

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

<p>It is implied NP-Hard by <a href="https://www.google.ca/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;cad=rja&amp;uact=8&amp;ved=0ahUKEwiVzrLzqq_LAhXFmIMKHZzBDHwQFggbMAA&amp;url=http%3A%2F%2Feccc.hpi-web.de%2Freport%2F2006%2F088%2Fdownload%2F&amp;usg=AFQjCNEd0NwBfa1vhvsEhxEjEq1EnJeogA&amp;sig2=un1ewatash0gQ9f48Imn_w&amp;bvm=bv.116274245,d.amc" rel="noreferrer">[this paper]</a>, 
but I can't find the original NP-Hardness proof.</p>

<p>Is it a consequence of the hardness of Max-2-SAT ?</p>

<p>Also as a bonus, Balanced Max-2-SAT($k$) is the subcase in which <em>every</em> 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.</p>

<np-hardness><sat><max2sat>
Balanced Max-2-SAT NP-Hardness
Manuel Lafond
# Balanced Max-2-SAT NP-Hardness

(Asked by: username_0 on 2016-03-07)

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]](https://www.google.ca/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwiVzrLzqq_LAhXFmIMKHZzBDHwQFggbMAA&url=http%3A%2F%2Feccc.hpi-web.de%2Freport%2F2006%2F088%2Fdownload%2F&usg=AFQjCNEd0NwBfa1vhvsEhxEjEq1EnJeogA&sig2=un1ewatash0gQ9f48Imn_w&bvm=bv.116274245,d.amc),
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.

**Tags:** np-hardness, sat, max2sat

---

## 1 answers

### Answer by username_1 on 2016-03-08. Score: 7 | Accepted 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.

> **Comments:**
> **username_0**: Marvelous, that seems to work!  

---

