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