Disconnecting a connected graph

Question

I need to find the minimum number of edges that need to be removed from a connected graph (which may have cycles and has unweighted undirected edges) so that i end up with two given nodes - A and B in separate disconnected parts.

Input: Edges, Node A, Node B. (There exists at least 1 path from A to B) Output: Minimum number of edges to be removed so that there remains no path between A & B

I can only think of the worst solution:-

best = no. of edges in the given connected graph G
For each possible subset S of Edges in the given connected graph G
   Graph temp = G minus edges S
   if there exists a path between A and B in temp
       continue
   else
        best = Min(best, no. of edges in S)
return best

I'm looking for a solution which would work comfortably for a graph with 15 vertices within a second or two. I wonder if my solution is good enough.

Thanks!

P.s. I'm not sure whether the big O complexity of my solution is 2^n or n*(2^n) or (n^2)*(2^n). I think its the latter but I would like to know for sure.

Answer 1

You can use a maximum flow algorithm to compute the minimum cut between A and B in your graph.

Runtime: O(n*m) with an excess-scaling push-relabel variant (since you have only unit capacities).

Your solution is O(2^m * (n + m)) if you use DFS or BFS for reachability in the fixed subgraph.