How can I check that a graph network contains an unique maximal flow? Are there any polynomial-time algorithms which can do that? Thanks!
Description:
Find all cuts between source and sink. For every cut, if there are two edges with minimum capacity, then the maximum cannot be unique. Return false. If all cuts have a single minimum capacity, then return true.
But I need a more efficient algorithm.
I need to know if a graph network has an unique maximal flow (I can send maximal flow from source to sink in only one way).
I'll suppose there isn't any vertex of degree 2 otherwise you can contract one of it's edge and update the capacity of the other one accordingly. Similar thing works for parallel edges. We can find an arbitrary maximum flow, then delete one edge from a flow in a graph. Check wether there still is another flow with same amount. If not, add back deleted edge and do same action for another edge. Unlike your previous attempt (finding all cuts, which can be exponential) this algorithm is polynomial in size of a gragh.