Skip to main content
added 142 characters in body
Source Link

The NP-complete Balanced min cut problem is a special case of your problem which is NP-complete ($|S|> c|V|$$|S|< c|V|$ and $|V-S|>c|V|$$|V-S|<c|V|$ for $0<c<1$) is a special case of your problem. Hence 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)

Balanced min cut problem is a special case of your problem which is NP-complete ($|S|> c|V|$ and $|V-S|>c|V|$ for $0<c<1$). Hence your problem is NP-complete.

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)

Source Link

Balanced min cut problem is a special case of your problem which is NP-complete ($|S|> c|V|$ and $|V-S|>c|V|$ for $0<c<1$). Hence your problem is NP-complete.