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?