Finding vertex separator such that the induced subgraph has minimal number of edges My problem is related to edge and vertex cuts with a little twist.
Given a graph $G$ and two vertexes $u$ and $v$. I want to find a set of vertexes $S \subset V$ that disconnects $u$ and $v$ such that the induced subgraph $G[S]$ has minimal number of edges.
Consider the following graph:

The red edges are the minimal edge cut. The blue vertices are the minimal vertex cut. The green vertices are a vertex cut such that the induced subgraph has the least number of edges. I try to find the green cut. In fact, the number of vertices is not required to be minimal as long as the number of edges in $G[S]$ are minimal.
Is there an algorithm in $P$ to solve this problem? Do you have an idea how to approach the problem?
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.