4
$\begingroup$

Let's say we a have flow network with $m$ edges and integer capacities.

Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.

A good way to start thinking about this is to imagine that we know the maximum flow already. How can we figure the sequence of $m$ paths?

$\endgroup$
  • $\begingroup$ Have you looked at runtime analyses of the Ford-Fulkerson algorithm? $\endgroup$ – Raphael Apr 14 '13 at 16:12
  • $\begingroup$ The run-time analysis shows that the upper limit for the iterations in "the loop" is determined by the maximum capacity C. In the worst case scenario with the increments of 1 the algorithm roughly runs C times. $\endgroup$ – 372 Apr 14 '13 at 18:25
  • $\begingroup$ why do you think this is true? $\endgroup$ – Sasho Nikolov Apr 14 '13 at 19:47
  • $\begingroup$ This is a problem from one of the books. I think it is obvious that the problem is not trivial $\endgroup$ – 372 Apr 14 '13 at 20:15
  • $\begingroup$ The Ford-Fulkense runtime analysis suggests the running time of O(N*f) where f is the largest flow in the network. This is natural because determination of a single path roughly takes O(N) and for integer maximum flow of f the algorithm iterates f times. So the non-trivial part is to prove that if paths were to be chosen in an optimal way the number of iterations would actually be N. $\endgroup$ – 372 Apr 14 '13 at 22:31
2
$\begingroup$

I got it myself... The idea is to set the flows of all edges to 0 one by one. It will take M iterations to do so. Once all edges are set to zero it becomes clear that the highest number of augmenting paths can not exceed the number of edges that are 0.And since there are M such edges the maximum number of possible paths is M as well.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Here is the solutions from my university exercise sheet. But frankly speaking I still don't get it...

Solution from my exercise sheet

| cite | improve this answer | |
$\endgroup$

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.