Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.

My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem. I don't know whether my solution is correct or not. Please help me check it:

  1. Replace each of the undirected edges with a pair of directed edges.
  2. Replace each vertex $v$ with two vertices $v_\text{in}$ and $v_\text{out}$ connected by an edge. all the incoming edges of $v$ will be connected with $v_\text{in}$, all the outgoing edges of $v$ will be connected with $v_\text{out}$.
  3. Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.
share|improve this question
It should work (I assume all edges have the same capacity). –  A.Schulz Dec 17 '12 at 9:26
thanks for your reply and editing. –  babysnow Dec 17 '12 at 15:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.