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.
Can we do this using say a max-flow, min-cut algorithm?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
(This answer was originally given as part of the question, with the goal of it being verified.)
My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem: