The MAX-CUT problem has constant factor approximation, but we can't control the sizes of the sets in resulting partition. What is known about maximizing cut size, if we restrict one part of the partition to have size exactly $k$?
Formally, given a graph $G(V, E)$ and integer $k$, find the set $S \subset V$, such that $|S| = k$ and the number of edges between $S$ and $V \setminus S$ is maximized. What is the name of this problem (for example, if $k = |V|/2$, this is known as MAX-BISECTION)? Does it become easier to approximate in polynomial time, if $k$ is $polylog(|V|)$?