Reason for global update steps in the push-relabel algorithm

Question

I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?

Answer 1

Global relabeling is not required; it's an optimization. In the push-relabel paper, Goldberg and Tarjan describe a parallel version not amenable to such an update. The kind of performance problem global relabeling addresses is when two nodes u and v with surplus and residual arcs to one another become disconnected from the sink in the residual graph. The local relabeling rule can only increase u's label to one more than v's, and vice versa, so surplus is pushed back and forth and the labels slowly count up until the maximum of n is reached. Now imagine if this happens to a dense subgraph with many nodes.

By alternating m steps of push/relabel with global updates, the running time at worst goes up by a constant factor but in practice typically goes down, by a lot. The best implementations of push-relabel use gap relabeling as well as global relabeling. Both heuristics are described, with some experiments, by Cherkassky and Goldberg.