Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

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?

share|improve this question
Have you looked at runtime analyses of the Ford-Fulkerson algorithm? – Raphael♦ Apr 14 at 16:12
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. – Adam Pflepinsky Apr 14 at 18:25
why do you think this is true? – Sasho Nikolov Apr 14 at 19:47
This is a problem from one of the books. I think it is obvious that the problem is not trivial – Adam Pflepinsky Apr 14 at 20:15
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. – Adam Pflepinsky Apr 14 at 22:31
show 3 more comments

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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