<p>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.</p>

CC BY-SA 4.0
2021-05-08T21:23:41.473Z
Brilliant, thank you! My take away is: in case of a fragile graph, an efficient algorithm that solves my problem above would find an independent cut. Thus, such an algorithm cannot exist unless P = NP.
Marian
CC BY-SA 4.0
2021-05-08T18:45:20.133Z
2021-05-08T18:45:20.133Z
David Eppstein
<p>My problem is related to edge and vertex cuts with a little twist.</p>
<p>Given a graph <span class="math-container">$G$</span> and two vertexes <span class="math-container">$u$</span> and <span class="math-container">$v$</span>. I want to find a set of vertexes <span class="math-container">$S \subset V$</span> that disconnects <span class="math-container">$u$</span> and <span class="math-container">$v$</span> such that the induced subgraph <span class="math-container">$G[S]$</span> has minimal number of edges.</p>
<p>Consider the following graph:</p>
<p><a href="https://i.sstatic.net/7CiOh.png" rel="noreferrer"><img src="https://i.sstatic.net/7CiOh.png" alt="enter image description here" /></a></p>
<p>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 <span class="math-container">$G[S]$</span> are minimal.</p>
<p>Is there an algorithm in <span class="math-container">$P$</span> to solve this problem? Do you have an idea how to approach the problem?</p>

<graph-theory><graph-algorithms><np-hardness><partition-problem><max-flow-min-cut>
Finding vertex separator such that the induced subgraph has minimal number of edges
Marian
# Finding vertex separator such that the induced subgraph has minimal number of edges

(Asked by: username_0 on 2021-05-08)

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:

[![enter image description here](https://i.sstatic.net/7CiOh.png)](https://i.sstatic.net/7CiOh.png)

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?

**Tags:** graph-theory, graph-algorithms, np-hardness, partition-problem, max-flow-min-cut


---

## 1 answers

### Answer by username_1 on 2021-05-08. Score: 11 | Accepted answer

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996)
217–222, as cited by Guantao Chen and Xingxing Yu, "A note on fragile graphs", 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.

> **Comments:**
> **username_0**: Brilliant, thank you! My take away is: in case of a fragile graph, an efficient algorithm that solves my problem above would find an independent cut. Thus, such an algorithm cannot exist unless P = NP.  

---

