Graph connectedness assignment

Question

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).

Answer 1

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.

Answer 2

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.

Answer 3

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.