0

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.

  • Lift 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!

Idra
  • 70

1 Answers1

0

In a preflow, at a certain moment, the potential excess to be pushed to $s$ is the sum of all $e(v), v \in V - \{s,t\}$, where $e$ is the net flow into a vertex, as defined in the original paper.

Here we define the sum of $e(v)$ aformentioned in a certain iteration as $p$, it can be shown that in a push operation between two vertices other than $s,t$, it is not changed. And it can only be reduced when pushing to $s$ or $t$. When push to $s$, $x_f(s)$ reduces as much as $p$ recudes. In other words, $p$ is the potential amount of reduction that might be applied to $s$.

As a result, during the whole execution, there does not exist a moment when $p$ can be larger than that after the initialization.

After the initialization, the sum of $e(v)$ is just equal to $x_f(s)$. That is it.

Scriabin
  • 31