# Push–Relabel Maximum Flow Algorithm $x_f(s)\leq0$

I'm looking at Push–Relabel Maximum Flow Algorithm (or Goldberg-Tarjan Algorithm) and trying to solve some homework question.
As part of the answer I'm trying to prove $x_{f}(s)\leq0$ during the entire algorithm run (where $s$ is the source, and $x_{f}:V\to\mathbb{R}$ is the excess function $x_{f}\left(u\right)=\underset{v\in V}{\sum}f\left(v,u\right)$ ).

I feel like this somehow should be trivial, but no matter what I've tried, I was unable to prove it.

I know pushes into $s$ are possible , just not sure how to show they don't make $x_{f}\left(s\right)>0$ .

I assume the proof would be by induction, as at the start $x_{f}\left(s\right)\leq0$ since the initialization step saturates all of $s$ 's adjancet nodes.

If we assume $x_{f}\left(s\right)\leq0$ , we have to show that after one iteration of the algorithm it still holds.

• Relabel is trivial since it doesn't change the flow.
• A Push from nodes unrelated to s is trivial as well.
• A Push from s to any other node would decrease $x_{f}\left(s\right)$ so that is trivial as well.
• I'm only left with the case $Push\left(u,s\right)$.

Help or direction would be appreciated,
Thanks!

• If you consider the valid labeling condition for $s$, you can see that $x_f(s)$ is always negative. – orezvani Apr 25 '17 at 1:30
• Can you please elaborate? – Ungoliant Apr 25 '17 at 1:41
• $s$'s neighbours can sometimes Push back to s. They can get a label that is greater than $s$, so I'm not sure how to use that... – Ungoliant Apr 25 '17 at 11:08