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.
    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
    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
    Jul 14, 2021 at 14:00
  • $\begingroup$ Thanks all, this answers my question. $\endgroup$
    – user3508551
    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 that you have read and understand our privacy policy and code of conduct.

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