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

Question

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

Answer 1

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

Answer 2

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