Java - Graph critical links

Question

I have a graph in which i have two nodes (0 and 6) and i have to cut the least edges possible so that they aren´t connected. For example in this graph

Being the nodes 0 and 6 the least edges that i have to cut are 2-7 and 3-7. My idea was finding the shortest path between the both using bfs, i find one (0-2-7-6) but then i don´t know how to find the other (0-3-7-6). Even then i have no idea how choose the edges to cut.

It would be nice if someone could give me some pointers on this matter.

Answer 1

This problem seems very similar to that of finding articulation nodes within a graph. The technical definition of an articulation point, or a biconnected component is a node whose removal would cause a graph to be split in two.

The discovery of articulated nodes from a graph is a largely solved problem and you can find more details about it here: http://en.wikipedia.org/wiki/Biconnected_component

It seems to me that the way you would like to approach a problem like this in general would something along these lines:

1. Find all articulation points
2. Do a bfs from each node and determine articulation points along the path
3. Split graph at the articulation point, choosing the side with minimal edges
4. Continue until the two nodes are not connected

In the above example, 7 is the only articulation point and so you would snip the edges between 7, 2 and 3 since there are only two edges between 7 and the 0-4 graph and 3 edges between 7 and the 5,6,8 graph.

There is a more established algorithm for doing this (read: one that I didn't come up with) called Karger's algorithm that can solve your problem, albeit in n^2 time.

That algorithm works by effectively joining adjacent nodes to each other until there are only two nodes and then by counting the number of edges left between the two nodes. The number of edges is then the minimum number of cuts required to split the graph.

The way you would implement Karger's algorithm in your problem would just need the caveat that you should always be joining nodes to the two nodes you want to split. Additionally, in order to be able to go backward to the original edges you need to cut you should keep a reference to which nodes the edges originally belonged to.

There's a great visualization of Karger's algorithm here: http://en.wikipedia.org/wiki/Karger%27s_algorithm

Answer 2

What you want is a min s-t cut. The usual way to find one in a general graph is to run an algorithm like push relabel with source 0 and sink 6, which computes a min s-t cut as a byproduct of computing a maximum flow.

Karger's algorithm finds a min cut, i.e., it minimizes over s and t as well as cuts. Since s and t are fixed for you, Karger's is not appropriate. An articulation vertex is a vertex whose removal disconnects the graph. You are interested in removing edges, not vertices.