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

Improve this question
$\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.
    Commented Jul 14, 2021 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
    Commented Jul 14, 2021 at 6:42
  • 3
    $\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$
    – Chandra Chekuri
    Commented Jul 14, 2021 at 14:00
  • $\begingroup$ Thanks all, this answers my question. $\endgroup$
    – user3508551
    Commented Jul 15, 2021 at 16:13

1 Answer 1

Reset to default
1
$\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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.