# Minimum cut with size bounds $k\leq |S| \leq |V|-k$

It is known by the max flow min cut theorem that the minimum cut problem is in $$P$$.

I am interested in knowing what is known on the complexity of the minimum cut with size $$k\leq |S| \leq , |V|- k$$. In other words, the minimum of $$\displaystyle \sum_{e\in \delta(S)}w_e$$ across all subsets $$S\subset V : k\leq |S| \leq |V|-k$$.

• The set of $s-t$ min-cuts forms a distributive lattice with operations intersection and union. I don't know if this structure can help solve this problem.
– D.W.
Jul 14 at 6:36
• Solving this for $k = c|V|$ for some constant $c$ would give a constant factor approximation of the balanced separator problem. Currently the best known is a $O(\sqrt{\log n})$ approximation (see here). There are inapproximability results for a slight generalization of the problem (see here). Jul 14 at 6:42
• $k= |V|/2$ is the min bisection problem which is NP-Hard. Best known approximation for min bisection is $O(\log n)$ (see Raecke's paper dl.acm.org/doi/abs/10.1145/1374376.1374415). However we have $O(\sqrt{\log n})$ for if $k = c V$ for any constant $c$, as already mentioned. Jul 14 at 14:00
• Thanks all, this answers my question. Jul 15 at 16:13

The NP-complete Balanced min cut problem ($$|S|< c|V|$$ and $$|V-S| for $$0) is a special case of your problem. Hence your problem is NP-complete.

Reference: Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976)