Reputation: 2818
Does anyone know an algorithm for the following problem:
Given a undirected connected graph find the number of ways in which 2 distinct edges can be cut such that the graph becomes disconnected.
I think a part of the problem (which I know an algorithm for) is calculating the number of ways in which 1 line can be cut so that it becomes disconnected. Then computing how these can be grouped with other lines gets the value (M-K)*K + K*(K-1)/2
, M
= no. of edges, K
= no. of 1 edge cuts.
The part that I don't know how to do is finding the number of other ways to cut 2 line, for example in the graph that has only the cycle 1 - 2 - 3 - 1
any combination of the edges is a valid way of cutting lines to make the graph disconnected.
I coded the part of the program that finds all the 1 edge cuts and then I split the graph into biconnected components by removing those edges. I tried writing something for the second part, made 2 versions for that, but none of them got the right answer on every test.
Additional information about this homework problem: * The number of edges is < 100,000 * The number of vertexes is < 2000 * The program should run maximum 2 seconds on any graph with the above restrictions * There can be multiple edges between 2 vertexes.
I can do the first part in O(N+M). I guess the complexity for the second part should be maximum O(N*M).
Upvotes: 2
Views: 933
Reputation: 450
This problem is an extension of the 2-edge connectivity problem. To make sure that any edge (v, w)
in the Graph is not a bridge, we find a back-edge from vertices adjacent to w and including w
going to ancestor of v
. Here, ancestor means the vertices which were discovered before v
.
Now, if there is only one such back-edge then that back-edge and (v, w)
when removed will make the graph disconnected.
Upvotes: 0
Reputation: 8004
The trivial solution: for all pairs of edges remove them from the graph and see if it is still connected. It's O(n^3) but should work.
Upvotes: 0
Reputation: 24180
You are looking for all edge cuts containing two edges. Such edge cuts only exist if the graph is at most 2-edge-connected.
The paper "Efficient algorithm for finding all minimal edge cuts of a nonoriented graph" by Karzanov and Timofeev contains an algorithm for computing all minimal edge cuts of a graph. From a brief look, it seems to me as if the algorithm can also be used to find cuts with a specified number of edges (for example, 2 edges). The complexity of the algorithm is O(lambda n^2), where lambda is the number of edges in the desired cuts (in your case, 2) and n is the number of vertices.
Upvotes: 7