2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

This is pseudocode, not the end-all be-all of the algorithm implementation. It is a very high level overview and by nature is left up to interpretation for the implementation. That being said...

"When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity."

This is not necessarily the case. You can analyze the residual graph in place, simply based on $f$ and $G$. By this, I mean it is not necessary to explicitly create a new graph $G_f$ because $G_f$ is merely a function of $G$ and $f$.

If this is the case, then the flow function $f$ is passed in to compute the residual capacity of each edge in the path. Similarly to how $G_f$ can be computed in place, if we have a path $P_f$ (from $s$ to $t$) in $G_f$, it doesn't necessarily have to an explicit path in $G_f$. It could be a path in $G$ for which we must compute $P_f$. This is when we might require $f$ to compute the bottleneck.

Again, this is just pseudocode and if you implement in a slightly different way than is described, that's okay as long as the procedure is correct.

$\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.