Thursday, November 17, 2011

The Initialization of the Generic Push-Relabel Algorithm

When we apply the generic push-relabel algorithm, we first label s as |V| and t as 0, and all edges starting from s are pushed in as many units of flow as possible, i.e they are saturated. But why these operations are necessary and reasonable is not stated explicitly.

What if we label s and t with different values? The difference between h[s] and h[t], h[s]-h[t], must be no smaller than |V|, for otherwise the statement that there is no path from s to t in the residual network never holds. And when the preflow becomes a flow, it is not necessarily a maximum flow since there may be augmenting paths. If s and t are labeled with greater values other than |V| and 0, the bounds on the number of relabel, saturating push and thus non-saturating push will become higher. Intuitively, there must be redundant relabel operations before extra flows are pushed to t or back to s since h[s] and h[t] become greater, and during that process, extra push operations between vertices other than s and t occur.

Suppose for some neighbor u of s, we initially push less flow into edge (s,u) than c(s,u). Then (s,u) is in the residual network. But h[s]=|V|>=2>h[u]+1=0+1=1, i.e. h is no longer a valid height function.

No comments:

Post a Comment