0
$\begingroup$

In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned:

To make the preflow a “legal” flow, the algorithm then sends the excess collected in the reservoirs of overflowing vertices back to the source by continuing to relabel vertices to above the fixed height |V| of the source. As we shall see, once we have emptied all the reservoirs, the preflow is not only a “legal” flow, it is also a maximum flow.

What does it mean to say "to make preflow a legal flow". Could someone elaborate on the same.

$\endgroup$

1 Answer 1

1
$\begingroup$

Inspecting the correctness proof and/or executing any non-trivial example, you'll note that push-relabel algorithms are different from Ford-Fulkerson and variants in that they do not maintain a flow; that's just not part of the invariant, and it's blatantly violated right at the start.

This whole "push flow to the sink, then push the excess back to the source" idea is only that: an idea. The algorithm does not really work like that, always. But it's still useful.

Once the "wave" reaches the sink $t$, it saturates the cut $V \setminus \{t\}$. You still have vertices with excess left¹, though; the conservation of flow property is violated. This has to be remedied before we can terminate with a flow -- hence the "push flow back to the source" phase.


  1. Whenever the cut $V \setminus \{s\}$ is not by coincidence a min-cut.
$\endgroup$
2
  • $\begingroup$ .Thanks for your explanation. I had one doubt though. You mentioned that "conservation of flow property is violated". What exactly is the conservation of flow property as per push relabel. In a normal max flow algorithm, the inflow into a node is equal to outflow from the node. What is it in case of push relabel? $\endgroup$
    – Vikas J
    Apr 16, 2016 at 16:55
  • $\begingroup$ "What exactly is the conservation of flow property" -- see the definition of "flow". The notion is not tied to what you call "normal" max-flow algorithms, by which you probably mean Ford-Fulkerson and variants. $\endgroup$
    – Raphael
    Apr 16, 2016 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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