Graph connectedness problem

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.

The number of edges is < 100 000 , and the number of vertexes is < 2000. The program should run maximum 2 seconds on any graph with the above restrictions. Also 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

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 2

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.