<p>The case where <span class="math-container">$\epsilon$</span> is a fixed constant in <span class="math-container">$(0,1)$</span> represents a partition that each part contains at least a constant fraction of the vertices. This was proven to be NP-complete by Wagner and Wagner. This is also known as balanced minimum cut problem. Note that <span class="math-container">$|V_i| \leq (1+\epsilon)|V|/2$</span> if and only if <span class="math-container">$|V_i| \ge (1-\epsilon)|V|/2$</span> for <span class="math-container">$\epsilon$</span> in <span class="math-container">$(0,1)$</span>.</p>

<p>Wagner D., Wagner F. (1993) <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.604&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Between Min Cut and Graph Bisection</a>. In: Borzyszkowski A.M., Sokołowski S. (eds) Mathematical Foundations of Computer Science 1993. MFCS 1993. Lecture Notes in Computer Science, vol 711. Springer, Berlin, Heidelberg</p>

CC BY-SA 4.0
2019-12-14T16:19:14.337Z
Exactly what I was looking for, thank you!
Timon Knigge
CC BY-SA 4.0
2019-12-14T05:52:47.487Z
2019-12-14T09:11:17.370Z
2019-12-14T09:11:17.370Z
Mohammad Al-Turkistany
<p>It appears <em>Finding good approximate vertex and edge partitions is NP-hard</em> by Thang Nguyen Bui and Curt Jones contains this result as well.</p>

CC BY-SA 4.0
2019-12-14T21:36:14.860Z
2019-12-14T21:36:14.860Z
Timon Knigge
<p>Consider this graph partitioning problem: Let <span class="math-container">$G = (V, E)$</span> be a simple undirected graph and <span class="math-container">$0 \leq \epsilon \leq 1, M \geq 0$</span>  be constants. Are there disjoint subsets <span class="math-container">$V_1, V_2$</span> with <span class="math-container">$V = V_1 \cup V_2$</span> and <span class="math-container">$|V_i| \leq (1+\epsilon)|V|/2$</span> such that at most <span class="math-container">$M$</span> edges have an endpoint in both sets?</p>

<p>In Computers and Intractability (1979), Garey and Johnson claim this problem is <span class="math-container">$NP$</span>-Complete (label: ND17) (they use an upperbound <span class="math-container">$B \geq 0$</span> requiring <span class="math-container">$|V_i| \leq B$</span>, but for us that just means setting <span class="math-container">$\epsilon= 2B/|V|-1$</span>).</p>

<p>Is anything known about the <span class="math-container">$NP$</span>-Completeness of this problem for fixed values of <span class="math-container">$\epsilon$</span>? For <span class="math-container">$\epsilon = 0$</span> we get the standard perfectly balanced bisection problem. For <span class="math-container">$\epsilon  = 1$</span> the problem is vacuously trivial. What if <span class="math-container">$\epsilon$</span> is some fixed constant in <span class="math-container">$(0, 1)$</span> (that is, not part of the input, but part of the problem definition).</p>

<reference-request><graph-theory><np-hardness><partition-problem>
$NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$
Timon Knigge
# $NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

(Asked by: username_0 on 2019-12-11)

Consider this graph partitioning problem: Let $G = (V, E)$ be a simple undirected graph and $0 \leq \epsilon \leq 1, M \geq 0$ be constants. Are there disjoint subsets $V\_1, V\_2$ with $V = V\_1 \cup V\_2$ and $|V\_i| \leq (1+\epsilon)|V|/2$ such that at most $M$ edges have an endpoint in both sets?

In Computers and Intractability (1979), Garey and Johnson claim this problem is $NP$-Complete (label: ND17) (they use an upperbound $B \geq 0$ requiring $|V\_i| \leq B$, but for us that just means setting $\epsilon= 2B/|V|-1$).

Is anything known about the $NP$-Completeness of this problem for fixed values of $\epsilon$? For $\epsilon = 0$ we get the standard perfectly balanced bisection problem. For $\epsilon = 1$ the problem is vacuously trivial. What if $\epsilon$ is some fixed constant in $(0, 1)$ (that is, not part of the input, but part of the problem definition).

**Tags:** reference-request, graph-theory, np-hardness, partition-problem


---

## 2 answers

### Answer by username_1 on 2019-12-14. Score: 4 | Accepted answer

The case where $\epsilon$ is a fixed constant in $(0,1)$ represents a partition that each part contains at least a constant fraction of the vertices. This was proven to be NP-complete by Wagner and Wagner. This is also known as balanced minimum cut problem. Note that $|V\_i| \leq (1+\epsilon)|V|/2$ if and only if $|V\_i| \ge (1-\epsilon)|V|/2$ for $\epsilon$ in $(0,1)$.

Wagner D., Wagner F. (1993) [Between Min Cut and Graph Bisection](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.604&rep=rep1&type=pdf). In: Borzyszkowski A.M., Sokołowski S. (eds) Mathematical Foundations of Computer Science 1993. MFCS 1993. Lecture Notes in Computer Science, vol 711. Springer, Berlin, Heidelberg

> **Comments:**
> **username_0**: Exactly what I was looking for, thank you!  

---

### Answer by username_0 on 2019-12-14. Score: 0

It appears *Finding good approximate vertex and edge partitions is NP-hard* by Thang Nguyen Bui and Curt Jones contains this result as well.


---

