One Possible Implementation of the Generic Push-Relabel Algorithm

The book said that we can select an applicable operation in O(1) time, and use O(V) and O(1) time for relabel and push operation respectively.

First note that all operations are performed on overflowing vertices other than s or t. We may store all these vertices in a data structure and when that structure becomes empty, the algorithm terminates. When nonempty, pick an arbitrary vertex u from it. If there is some admissible edge (u,v)(that is, (u,v) is in the residual network and h[u]=h[v]+1), a push operation is applicable. Otherwise, a relabel operation is applicable.

So we may wish to maintain a list of admissible edges for every vertex. Every time, either a push or relabel operation may be applicable depending on whether the corresponding list is empty or not. After a push, the only possible influence on these lists is that (u, v) has to be removed from the list corresponding to u after a saturating push. If we simply associate every edge a pointer to the nodes in these lists, the removal can be done in O(1) time. Each edge (u,v) may appear in these lists at most once, for h[u]=h[v]+1 and h[v]=h[u]+1 cannot hold at the same time.

But after a relabel operation on u, some edges (u,v) has to be inserted into the list corresponding to u, and all edges (v,u) appearing in other lists has to be removed. The insertion is simple. But we have to check the lists for every other vertex in order to remove edges ending at u, thus resulting in O(E) time complexity. The solution is to use orthogonal lists. Intuitively, all admissible edges leaving u are on the horizontal line, while those entering u are on the vertical line. Now, the insertion and removal operations take time proportional to the out degrees and in degrees of vertex u. A single operation of both types is now a little bit more complicated, but requires only O(1) time.

Finally, a simple list suffices for the data structure mentioned in the second paragraph. Every time, pick the vertex at the end of that list. Relabel doesn't change the flow of any vertex, so no updates are necessary. After a push from u to v, remove u if it is no longer overflowing and insert v if its flow is 0 previously.

Now, the generic push-relabel algorithm is implemented using a total time of O(V²E).