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


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

  • $\begingroup$ Exactly what I was looking for, thank you! $\endgroup$ – 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.


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.