3
$\begingroup$

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)

$\endgroup$
  • 2
    $\begingroup$ I think, you need to look for cycles in the residual graph. $\endgroup$ – Albjenow Nov 18 '19 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 vh Nov 18 '19 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$ – Albjenow Nov 18 '19 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_hacker Nov 20 '19 at 0:05
  • 1
    $\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_hacker Nov 20 '19 at 0:17
4
$\begingroup$

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.

$\endgroup$
  • $\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$ – narek Bojikian Nov 19 '19 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$ – j_random_hacker Nov 20 '19 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$ – j_random_hacker Nov 20 '19 at 0:14
  • 1
    $\begingroup$ @j_random_hacker: Thanks for the correction. Updated. $\endgroup$ – tjhighley Nov 21 '19 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$ – Optidad Nov 21 '19 at 11:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.