why does relabel take O(VE) time total for unit capacity flow networks?

Question

It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ relabelling operations per vertex, each taking $O(V)$ time, for a total of $O(V^3)$ for all relabelling operations.

I'm interested in what happens to these bounds when we restrict edge capacities to be 1. It is clear that there are no more non-saturating pushes, so only saturating pushes, of which there are always $O(VE)$, remain.

However, I found a 1995 phd thesis by a student of Goldberg that claims (on p 13) that when edge capacities are 1 (and thus all pushes are saturating), the relabelling portion takes $O(VE)$ time instead of the usual $O(V^3)$.

How does this $O(VE)$ result follow?

Answer 1

The $O(VE)$ result actually holds in general, not just for unit edge capacity, hence it has nothing to do with edge capacity being 1.

This result is proven in Exercise 26.4-3 of CLRS, and thus the $O(V^3)$ quoted in the question is not tight.