2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 14 at 6:36
  • 3
    $\begingroup$ 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). $\endgroup$
    – smapers
    Jul 14 at 6:42
  • 2
    $\begingroup$ $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. $\endgroup$ Jul 14 at 14:00
  • $\begingroup$ Thanks all, this answers my question. $\endgroup$ Jul 15 at 16:13
0
$\begingroup$

The NP-complete Balanced min cut problem ($|S|< c|V|$ and $|V-S|<c|V|$ for $0<c<1$) 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)

$\endgroup$

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.