8
$\begingroup$

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

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Marian
    May 8, 2021 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.