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)
6
-
3$\begingroup$ I think, you need to look for cycles in the residual graph. $\endgroup$– AlbjenowCommented Nov 18, 2019 at 7:17
-
$\begingroup$ @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? $\endgroup$– hh vhCommented Nov 18, 2019 at 15:23
-
$\begingroup$ 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. $\endgroup$– AlbjenowCommented Nov 18, 2019 at 15:51
-
1$\begingroup$ 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.) $\endgroup$– j_random_hackerCommented Nov 20, 2019 at 0:05
-
2$\begingroup$ 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 ;) $\endgroup$– j_random_hackerCommented Nov 20, 2019 at 0:17
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
5
Find a maximum flow. Then create m new flow networks: one for each edge in the maximum flow. In each new configuration, reduce the capacity of one of the edges to an amount just below its flow. Find the maximum flow on each of the new flow networks. If any of the new configurations generate the same maximum flow value as the original graph, then that new flow is also a maximum flow in the original graph. Hence, the original maximum flow is not unique.
-
1$\begingroup$ What is the smallest increment? And how do we prove that we do not generate a false positive (we do not prevent other maximum flows from occuring)? $\endgroup$ Commented Nov 19, 2019 at 22:07
-
3$\begingroup$ Reducing the capacity by a small amount only works for tight (at-capacity) edges; for non-tight edges with nonzero flow, you need to reduce capacity to just below that flow. $\endgroup$ Commented Nov 20, 2019 at 0:13
-
1$\begingroup$ @narekBojikian: Assuming integer flows, it's enough to multiply all existing capacities by 2 first, find a max flow for which all flows are even numbers (this must exist), and then try reducing the capacity of each edge with nonzero flow to one less than its flow. Rational flows can be handled similarly by first multiplying each capacity by all denominators to get integer flows. I don't know if something like this will work for irrational flows, but we usually don't have to deal with them in practice, and at least some Ford-Fulkerson algorithms can't find a max flow on these anyway. $\endgroup$ Commented Nov 20, 2019 at 0:14
-
1$\begingroup$ @j_random_hacker: Thanks for the correction. Updated. $\endgroup$ Commented Nov 21, 2019 at 0:32
-
2$\begingroup$ great but you should reformulate the answer. I hardly understood that one configuration comes from every one-edge capacity reduction. $\endgroup$– OptidadCommented Nov 21, 2019 at 11:47