At any point during the execution of the Edmonds-Karp algorithm:
- Define the shortest path in-degree of a vertex v to be
the number of edges coming in to v that are on shortest paths
from the source to v in the residual graph.
Let
denote v's shortest-path in-degree. - Let
denote the distance of v from the source
in the residual graph. - Define potential function
to be
.
(a) Show that this potential function increases with every round of
the Edmonds-Karp algorithm. Conclude that the number of rounds
is 
.
(b) Modify the potential function to improve the bound to O(V E).
(a) 
lift operations and saturating pushes
(b) (Extra Credit) 
nonsaturating pushes.
, a capacity c(e) > 0.
For the minimum-cost flow problem, one is also given
a cost 
for each edge .
The cost of a flow f on G is defined to be
The goal is to find a maximum flow that is of minimum cost among all maximum flows.
In the residual graph 
(as defined in the book for the maximum-flow problem),
define the cost 
of each edge 
to be -w(v,u) if f(v,u)>0, or w(u,v) otherwise.
(a) Prove that if the residual graph 
for a flow f
contains no negative cost cycle (with respect to the cost function 
)
then f is a minimum-cost flow among flows of value |f|.
(b) Among all 
paths in the residual graph, let p
be a shortest path, with respect to the cost function .
Prove that augmenting the flow f by sending flow along p
yields a flow f' that is of minimum-cost among all flows of value |f'|.
(c) Why does this imply that in a network with integer capacities, there is always an integer minimum-cost maximum flow?