8
$\begingroup$

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?

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

3 Answers 3

Reset to default
6
$\begingroup$

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.)

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Nov 11, 2010 at 13:40
  • $\begingroup$ Can you please elaborate on the algorithm? Any reference will be very helpful. $\endgroup$
    – Arindam Pal
    Feb 28, 2014 at 5:35
5
$\begingroup$

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.
Improve this answer
$\endgroup$
1
  • $\begingroup$ I also felt the same. Can you think about any reference in this regard? $\endgroup$
    – Rajat
    Aug 31, 2016 at 1:31

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.