Finding vertex separator such that the induced subgraph has minimal number of edges
An independent set that disconnects its graph is called an &quot;independent cut&quot;, graphs that contain an independent cut are called &quot;fragile graphs&quot;, and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, &quot;NP-completeness of multipartite cutset testing&quot;, Congr. Numer. 119 (1996)
217–222, as cited by Guantao Chen and Xingxing Yu, &quot;A note on fragile graphs&quot;, Discrete Math. 2002, https://doi.org/10.1016/S0012-365X(01)00226-6]. So your problem is hard even in the special case of zero edges.