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