Check if theres a single minimum cut in a given network flow

Question

I'm looking for an algorithms that checks if there's a signle minimum cut in a given network flow.

I know it's possible since we can look for all of the cuts, and check if we have only 1 minimum cut, but I want to find more efficient algorithm which runs polynomially.

I thought about using a max-flow algorithm in order to help me, but I didn't success.

Answer 1

I assume you are referring to the weighted case, if not - the unweighted can be reduced to the weighted pretty easily by giving weights of 1 to all edges.

One approach is to find one min cut, let it be a split U1,U2, and then for each pair of vertices u1 from U1 and u2 from U2, such that (u1,u2) is in E - check if by increasing slightly the weight w(u1,u1) - there is still a min cut with the same value.
At the end, if and only if you found one edge such that the min cut value remains - there is more then one min-cut.

High level pseudo-code:

value,U1,U2 = min-cut(G) //value is the minimum cut value, U1,U2 are the cuts
for each u1 in U1 and u2 in U2 such that (u1,u2) is in E:
   temp <- w(u1,u2)
   w(u1,u2) <- w(u1,u2) + epsilon
   new_value,_,_ = min-cut(G)
   if (new_value == value): //2+ cuts with same value
        return true
   //roll back the changed weight
   w(u1,u2) <- temp
return false //no cuts with same value found

Complexity is O(E*min-cut), where min-cut is the complexity of the used min-cut algorirthm