# Minimum cut through vertices/nodes - not edges

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?

• This smells like homework. (I just covered this in class last week.) Nov 11, 2010 at 15:08
• @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? Nov 11, 2010 at 15:26
• homework questions are not welcome on this site, that is the reason for Jeff's comment. Nov 12, 2010 at 11:17

See, for example, p. 205 and Theorem 11.7 of Bondy and Murty's Graph Theory with Applications (1976).

"Menger's 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.)

You are looking for Minimum Vertex K-cut. Also, if you search for k-node-connectivity you will get papers related to the structural properties of such cuts.

• 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. Nov 11, 2010 at 13:40
• Can you please elaborate on the algorithm? Any reference will be very helpful. Feb 28, 2014 at 5:35

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.

• I also felt the same. Can you think about any reference in this regard? Aug 31, 2016 at 1:31