<p>The NP-complete Balanced min cut problem (<span class="math-container">$|S|&lt; c|V|$</span> and <span class="math-container">$|V-S|&lt;c|V|$</span> for <span class="math-container">$0&lt;c&lt;1$</span>) is a special case of your problem. Hence your problem is NP-complete.</p>
<p>Reference: Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1, 237–267 (1976)</p>

CC BY-SA 4.0
2021-07-16T14:16:10.080Z
2021-07-16T14:30:07.197Z
2021-07-16T14:30:07.197Z
Mohammad Al-Turkistany
<p>It is known by the max flow min cut theorem that the minimum cut problem is in <span class="math-container">$P$</span>.</p>
<p>I am interested in knowing what is known on the complexity of the minimum cut with size <span class="math-container">$k\leq |S| \leq , |V|- k$</span>. In other words, the minimum of <span class="math-container">$\displaystyle \sum_{e\in \delta(S)}w_e$</span> across all subsets <span class="math-container">$S\subset V : k\leq |S| \leq |V|-k$</span>.</p>

CC BY-SA 4.0
2021-07-14T06:36:33.227Z
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.
CC BY-SA 4.0
2021-07-14T06:42:42.127Z
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](https://dl.acm.org/doi/10.1145/1502793.1502794)). There are inapproximability results for a slight generalization of the problem (see [here](https://cs.nyu.edu/~khot/papers/gl-journal-ver1.pdf)).
smapers
CC BY-SA 4.0
2021-07-14T14:00:53.363Z
$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 https://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.
Chandra Chekuri
CC BY-SA 4.0
2021-07-15T16:13:04.323Z
Thanks all, this answers my question.
user3508551
<cc.complexity-theory><max-flow-min-cut><max-cut>
Minimum cut with size bounds $k\leq |S| \leq |V|-k$
user3508551
# Minimum cut with size bounds $k\leq |S| \leq |V|-k$

(Asked by: username_0 on 2021-07-14)

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

**Tags:** cc.complexity-theory, max-flow-min-cut, max-cut
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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](https://dl.acm.org/doi/10.1145/1502793.1502794)). There are inapproximability results for a slight generalization of the problem (see [here](https://cs.nyu.edu/~khot/papers/gl-journal-ver1.pdf)).  
> **username_3**: $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 https://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.  
> **username_0**: Thanks all, this answers my question.  

---

## 1 answers

### Answer by username_4 on 2021-07-16. Score: 1

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)


---

