Skip to main content
2 of 2
edited tags

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

user3508551
  • 1.2k
  • 5
  • 14