Remove minimum edges in a graph such that given vertices are disconnected

Given an undirected graph and there are some edges connecting the nodes. There can be path between two nodes. We have to disconnect two nodes by removing the minimum number of edges. What is the best algorithm to solve this problem?

2 Likes

This can be done by Ford Fulkerson min-cut algorithm.

A good description of solution to the above problem is there at this link - http://myitlearnings.com/?p=13

I think dfs will work … :slight_smile:

DFS will work but the complexity would be very high.

i searched on net but could not find the proper algo. Can u please give some reference of that.

1 Like

vikasnitt: Simply put, while (there’s a flow) do: find a path along which you can push a flow of 1 unit (basically just a path along edges that don’t have flow=capacity, by DFS), then push that flow along that path. And considering how I learned it by searching around the net, I won’t believe you.