# how to check whether a flow network contains unique maximum flow?

I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum flow or not. I have been search everything I could, and some people said run an algorithm that able to find a max flow first, then modified the edges capacity, and run the algorithm one more time to see if we get the same flow value. But this seems never works for me especially when we are given arbitrary flow network, like non-integer flow graph. How should I start a good approach? (Literally stuck for few hours)

• I think, you need to look for cycles in the residual graph. Nov 18, 2019 at 7:17
• @Albjenow I have also seen this suggestion, like create a residual graph and run DFS to detect cycle. If there's no cycle then this max flow is unique. I haven't think that deep on this, but what is a flow is not saturated and it has back ward edge on the residual graph, isn't a cycle between two vertex? Nov 18, 2019 at 15:23
• That case could be interpreted as follows (at least in the integer capacity case): Suppose you have distinct items that could be pushed over an edge. If the edge is not saturated, i. e. not every item is delivered, but only some of them, any subset of the items consitutes a unique flow. Nov 18, 2019 at 15:51
• If the capacities are rational numbers, they can be turned into integers by multiplying every capacity by the denominators of all capacities. (Actually it suffices to multiply by the lowest common multiple of these denominators.) Nov 20, 2019 at 0:05
• It's easy to show that a cycle in the residual graph implies multiple maximum flows, but harder to show that multiple maximum flows implies a cycle in the residual graph ;) Nov 20, 2019 at 0:17