# $NP$-Completeness of $\epsilon$-balanced graph partitioning for fixed $\epsilon$

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).

## 2 Answers

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

• Exactly what I was looking for, thank you! – Timon Knigge Dec 14 '19 at 16:19

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