Question

I am looking at the following pseudocode from the Kleinberg-Tardos text "Algorithm Design".

Max-Flow
Initially f(e)=0 for all e in G
While there is an s-t path in the residual graph G_f
    Let P be a simple s-t path in G_f
    f' = augment(f,P)
    Update f to f'
    Update the residual graph G_f to be G_f'
Endwhile
Return f

This seems to make sense to me. However, prior to displaying this pseudocode, the textbook gives pseudocode for the augment subroutine:

augment(f,P)
Let b = bottleneck(P,f)
For each edge (u,v) in P
    If e = (u,v) is a forward edge then
        increase f(e) in G by b
    Else ((u,v) is a backward edge, and let e = (v,u))
        decrease f(e) in G by b
    Endif
Endfor
Return(f)

Unfortunately, the textbook does not give any implemenation details on the bottleneck() subroutine.

But what I cannot understand is why we would need to pass the flow function $f$, to the bottleneck subroutine?

It seems that the bottleneck routine is looking at a simple s-t path in the residual graph $G_f$. Hence bottleneck is only concerned with the residual capacity along each edge. When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity. Hence, a call such as bottleneck($P$) would seem to suffice which simply looked for the minimum capacity along the edges in $P$.

Can someone shed any light on why we pass $f$ to this bottleneck subroutine?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top