On Wed, Apr 14, 2004 at 03:11:22PM -0400, Michael Kleber wrote:
Jim Hendrickson of the chemistry department here just asked me whether there was a good algorithm for finding the set of all one- or two-edge cut sets of a graph. When pressed, he said he'd actually like to find the cut which leaves two pieces as close to the same size as possible.
An almost equivalent way to state the problem is that you're trying to find the 2-connected or 3-connected components of the graph. (A 2-connected graph is one that remains connected after removing any one edge; a 3-connected graph is one that remains connected after removing any two edges.) A related problem is to find sets of vertices that can be removed. According to http://citeseer.ist.psu.edu/hegde02finding.html the one-vertex cut sets "can be found easily by depth-first search", and for the two-vertex case you should see Hopcroft, J. E. and Tarjan, R. E., \Dividing a Graph into Triconnected Components ", SIAM J. Comput. 2 (1973), No. 3, 135-158. which is not online. I imagine the case for removing edges is similar. OK, after 30 seconds of thought, here's the algorithm for finding all edges that can be removed to disconnect the graph. Start by finding a spanning tree for the graph, and mark all components as belonging to different 2-connected components. Then, for each edge not in the spanning tree, find the path within the spanning tree between its two endpoints, and merge the 2-connected components of the vertices along that path. The edges that join different 2-connected components are the edges you're looking for. (These edges are necessarily in every spanning tree.) Peace, Dylan