<p>See, for example, p. 205 and Theorem 11.7 of Bondy and Murty's <em><a href="http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html">Graph Theory with Applications</a></em> (1976).</p>

<p>"<a href="https://secure.wikimedia.org/wikipedia/en/wiki/Menger%27s_theorem">Menger's theorem</a>" is a good keyword for further googling. The usual max-flow min-cut theorem implies the edge-connectivity version of the theorem, but you are interested in the vertex-connectivity version.</p>

<p>(These are existential results, but a typical proof of the vertex-connectivity version reduces the problem to the edge-connectivity version, and then you can apply efficient max-flow/min-cut algorithms.)</p>

CC BY-SA 2.5
2010-11-11T13:47:25.697Z
2010-11-11T13:47:25.697Z
Jukka Suomela
<p>You are looking for <a href="http://www.ensta.fr/~diam/ro/online/viggo_wwwcompendium/node91.html">Minimum Vertex K-cut</a>. Also, if you search for <a href="http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29">k-node-connectivity</a> you will get papers related to the structural properties of such cuts.</p>

CC BY-SA 2.5
2010-11-11T13:40:59.527Z
Your link to "Minimum Vertex K-cut" points to a definition of a *hard* problem (and related approximability results). Minimum vertex cut can be solved in polynomial time.
Jukka Suomela
CC BY-SA 3.0
2014-02-28T05:35:32.643Z
Can you please elaborate on the algorithm? Any reference will be very helpful.
Arindam Pal
CC BY-SA 2.5
2010-11-11T12:17:20.750Z
2010-11-11T12:17:20.750Z
Shiva Kintali
<p>It is not very difficult to transform the vertices problem to an equivalent edge version.</p>

<pre><code>Consider a vertex v. Replace v with v1 and v2. 
Join v1 and v2 with an edge of capacity 1.
All the incoming edges into v go into v1 and all the outgoing edges from v, leave v2.
ie (u v) -&gt; (u v1) and (v w) -&gt; (v2 w)
This is equivalent to edge version of the s-t min cut algorithm.
</code></pre>

CC BY-SA 3.0
2016-08-31T01:31:48.817Z
I also felt the same. Can you think about any reference in this regard?
Rajat
CC BY-SA 3.0
2015-11-04T21:22:20.157Z
2015-11-04T21:22:20.157Z
Pradeep Vairamani
<p>we all know and love s-t minimum cut algorithms, but they all cut through the edges in the graph. Are there any variants that cuts through nodes?</p>

CC BY-SA 2.5
2010-11-11T15:08:03.043Z
This smells like homework.  (I just covered this in class last week.)
Jeffε
CC BY-SA 2.5
2010-11-11T15:26:18.420Z
@JeffE: Sure, I'm a student and this is for a project - but there is no harm in asking, right? If one does not know what to search for, this is OK?
johan
CC BY-SA 2.5
2010-11-12T11:17:52.677Z
homework questions are *not* welcome on this site, that is the reason for Jeff's comment.
Kaveh
<ds.algorithms><graph-theory><max-flow-min-cut>
Minimum cut through vertices/nodes - not edges
johan
# Minimum cut through vertices/nodes - not edges

(Asked by: username_0 on 2010-11-11)

we all know and love s-t minimum cut algorithms, but they all cut through the edges in the graph. Are there any variants that cuts through nodes?

**Tags:** ds.algorithms, graph-theory, max-flow-min-cut

> **Comments:**
> **username_1**: This smells like homework.  (I just covered this in class last week.)  
> **username_0**: @JeffE: Sure, I'm a student and this is for a project - but there is no harm in asking, right? If one does not know what to search for, this is OK?  
> **username_2**: homework questions are *not* welcome on this site, that is the reason for Jeff's comment.  

---

## 3 answers

### Answer by username_3 on 2010-11-11. Score: 6 | Accepted answer

See, for example, p. 205 and Theorem 11.7 of Bondy and Murty's *[Graph Theory with Applications](http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html)* (1976).

"[Menger's theorem](https://secure.wikimedia.org/wikipedia/en/wiki/Menger%27s_theorem)" is a good keyword for further googling. The usual max-flow min-cut theorem implies the edge-connectivity version of the theorem, but you are interested in the vertex-connectivity version.

(These are existential results, but a typical proof of the vertex-connectivity version reduces the problem to the edge-connectivity version, and then you can apply efficient max-flow/min-cut algorithms.)


---

### Answer by username_4 on 2010-11-11. Score: 6

You are looking for [Minimum Vertex K-cut](http://www.ensta.fr/~diam/ro/online/viggo_wwwcompendium/node91.html). Also, if you search for [k-node-connectivity](http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29) you will get papers related to the structural properties of such cuts.

> **Comments:**
> **username_3**: Your link to "Minimum Vertex K-cut" points to a definition of a *hard* problem (and related approximability results). Minimum vertex cut can be solved in polynomial time.  
> **username_5**: Can you please elaborate on the algorithm? Any reference will be very helpful.  

---

### Answer by username_6 on 2015-11-04. Score: 6

It is not very difficult to transform the vertices problem to an equivalent edge version.
Consider a vertex v. Replace v with v1 and v2. 
Join v1 and v2 with an edge of capacity 1.
All the incoming edges into v go into v1 and all the outgoing edges from v, leave v2.
ie (u v) -> (u v1) and (v w) -> (v2 w)
This is equivalent to edge version of the s-t min cut algorithm.

> **Comments:**
> **username_7**: I also felt the same. Can you think about any reference in this regard?  

---

