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,

  • $\begingroup$ If you consider the valid labeling condition for $s$, you can see that $x_f(s)$ is always negative. $\endgroup$ – orezvani Apr 25 '17 at 1:30
  • $\begingroup$ Can you please elaborate? $\endgroup$ – Ungoliant Apr 25 '17 at 1:41
  • $\begingroup$ $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... $\endgroup$ – Ungoliant Apr 25 '17 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.