<p>This problem is called <em>weighted vertex connectivity</em>. See for instance "Computing Vertex Connectivity: New Bounds from Old Techniques" by Henzinger, Rao and Gabow (<a href="https://www.sciencedirect.com/science/article/pii/S0196677499910556" rel="nofollow noreferrer">link</a>).</p>

CC BY-SA 4.0
2019-06-06T12:37:45.497Z
2019-06-06T12:37:45.497Z
smapers
<p>I have an undirected graph <code>G</code> with a set of vertices and edges. Each vertex has a weight <em>w</em>. Let's assume we have all vertices connected with some paths. I'm looking for a variant of the min-cut problem. I search for a subdivision of the graph into two parts which are connected by a group of vertices which weights sum up to a minimum value. Can you give me a pointer or a name to the problem (if it exists already)? </p>

<graph-theory><graph-algorithms>
Min Cut with Vertices
michip96
# Min Cut with Vertices

(Asked by: username_0 on 2019-06-06)

I have an undirected graph `G` with a set of vertices and edges. Each vertex has a weight *w*. Let's assume we have all vertices connected with some paths. I'm looking for a variant of the min-cut problem. I search for a subdivision of the graph into two parts which are connected by a group of vertices which weights sum up to a minimum value. Can you give me a pointer or a name to the problem (if it exists already)?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2019-06-06. Score: 3 | Accepted answer

This problem is called *weighted vertex connectivity*. See for instance "Computing Vertex Connectivity: New Bounds from Old Techniques" by Henzinger, Rao and Gabow ([link](https://www.sciencedirect.com/science/article/pii/S0196677499910556)).


---

