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. Anyone know a good way to do this? I think anything better than brute force would count as "good". (The graphs he's interested in are ones that indicate bonded atoms in a molecule, so each vertex has degree at most four.) --Michael Kleber kleber@brandeis.edu
(The graphs he's interested in are ones that indicate bonded atoms in a molecule, so each vertex has degree at most four.)
Not that it mattes, but I was confused by this last comment. For random counterexample, uranium hexafluoride comes to mind. Did you mean to say organic molecule? But even so, there's organo-metallics, chelates, etc.
On Apr 14, 2004, at 3:27 PM, Marc LeBrun wrote:
(The graphs he's interested in are ones that indicate bonded atoms in a molecule, so each vertex has degree at most four.)
Not that it mattes, but I was confused by this last comment. For random counterexample, uranium hexafluoride comes to mind. Did you mean to say organic molecule? But even so, there's organo-metallics, chelates, etc.
I suppose he means that all the molecules he'll be looking at have this property -- <=4-valent carbons and lower valence other things... --Michael Kleber kleber@brandeis.edu
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
I had asked:
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. And Dylan algorithm'd: 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.)
Ah, quite right. Along similar lines, I came up with the following for the two-edge cut sets. Build a spanning tree and a matrix which lets you easily walk between any pair of vertices along the tree, just as you say. Each edge in the tree is assigned a list, initially empty, of its "cut partners". Then for each edge e not in the tree, walk along the tree between e's two endpoints and add e to the list of "cut parnters" of each edge you use. At the end, any edge in the tree whose cut-partner list is of length 0 is a cut edge, and any whose list is of length 1 is half of a two-edge cut set, with the list's sole element being the other edge you need to cut. It may not be deep, but it's quick... --Michael Kleber kleber@brandeis.edu
On Mon, Apr 19, 2004 at 11:43:19AM -0400, Michael Kleber wrote:
Ah, quite right. Along similar lines, I came up with the following for the two-edge cut sets. Build a spanning tree and a matrix which lets you easily walk between any pair of vertices along the tree, just as you say. Each edge in the tree is assigned a list, initially empty, of its "cut partners". Then for each edge e not in the tree, walk along the tree between e's two endpoints and add e to the list of "cut parnters" of each edge you use. At the end, any edge in the tree whose cut-partner list is of length 0 is a cut edge, and any whose list is of length 1 is half of a two-edge cut set, with the list's sole element being the other edge you need to cut.
I don't think that's correct in all cases. In particular, you sometimes miss two-edge cut sets. Consider a graph that's just a big loop, for instance. Cutting any two edges disconnects the graph (total of (n choose 2) pairs), but you only find n-1 pairs. Worse, you sometimes fail to find two-edge cut sets altogether: consider the graph with n vertices with one edge from k to k+1 and two edges from 1 to n, with the spanning tree consisting of all the edges from k to k+1. Then each edge in the spanning tree ends up with two cut partners, although there are plenty of two-edge cut sets. Peace, Dylan
participants (3)
-
dpt＠exoskeleton.math.harvard.edu -
Marc LeBrun -
Michael Kleber