Splay Trees:Case Study: Application to Network Flows

Case Study: Application to Network Flows

We next discuss application of linking and cutting trees to the problem of finding maximum flow in a network. Input is a directed graph G = (V, E). There are two distinguished vertices s (source) and t (sink). We need a few definitions and some notations[1, 6]. Most of the results in this case-study are from[1, 6].

Active Vertex A vertex v j= s is said to be active if e(v) > 0.

The initial preflow is taken to be g(s, v) = c(s, v) and g(u, v) = 0 if u j= s.

Flow across a Cut Please refer to Figure 12.6. Observe that flow conservation is true for all vertices except s and t. In particular sum of flow (total flow) into vertices in set S − {s} (set shown between s and cut) is equal to |f | which must be the flow going out of these vertices (into the cut). And this is the flow into vertices (from cut) in set S − {t} (set after cut before t) which must be equal to the flow out of these vertices into t. Thus, the flow into t is |f | which is also the flow through the cut.

Proof Consider a flow f for which |f | is maximum. Delete all edges for which (f (u, v) == c(u, v)) to get the residual graph. Let S be the set of vertices reachable from s in the residual graph. Now, t ∈/ S, otherwise there is a path along which flow can be increased, contradicting the assumption that flow is maximum. Let S be set of vertices not reachable from s. S is not empty as t ∈ S. Thus, (S, S) is an s − t cut and as all edges (v, w) of cut

Preflow-Push Algorithms

Following are some of the properties of preflow-push algorithms:

1. If relabel v results in a new label, d(v) = d(w∗ ) + 1, then as initial labeling was valid, dold(v) ≤ dold(w∗) + 1. Thus labels can only increase. Moreover, the new labeling is clearly valid.

2. If push is saturating, edge (v, w) may get deleted from the graph and edge (w, v) will get added to the residual graph, as d(w) = d(v) − 1, d(v) = d(w) + 1 ≥ d(w) − 1, thus even after addition to the residual graph, conditions for labeling to be valid are satisfied.

3. As a result of initialization, each node adjacent to s gets a positive excess. More- over all arcs out of s are saturated. In other words in residual graph there is no path from s to t. As distances can not decrease, there can never be a path from s to t. Thus, there will be no need to push flow again out of s.

4. By definition of pre-flow, flow coming into a node is more than flow going out.

This flow must come from source. Thus, all vertices with positive excess are reachable from s (in the original network). Thus, as s is initially the only node, at any stage of the algorithm, there is a path Pv to a vertex v (in the original network) along which pre-flow has come from s to v. Thus, in the residual graph, there is reverse path from v to s.

5. Consider a vertex v from which there is a path till a vertex X. As we trace back this path from X, then distance label d( ) increases by at most one. Thus, d(v) can be at most dist(v, X) larger than d(X). That is d(v) ≤ d(X)+ dist(v, X)

6. As for vertices from which t is not reachable, s is reachable, d(v) ≤ d(s)+ dist(s, v) = n + (n − 1) = 2n − 1 (as d(s) = n).

Thus, maximum label of any node is 2n − 1.

FACT 12.5 As label of t remains zero, and label of other vertices only increase, the number of Relabels, which result in change of labels is (n − 1)2. In each relabel operation we may have to look at degree(v) vertices. As, each vertex can be relabeled at most O(n) times, time for relabels is ), O(n)×degree(v) = O(n) × ), degree(v) = O(n) × O(m) = O(nm)

FACT 12.6 If a saturating push occurs from u to v, then d(u) = d(v)+ 1 and edge (u, v) gets deleted, but edge (v, u) gets added. Edge (u, v) can be added again only if edge (v, u) gets saturated, i.e., dnow(v) = dnow (u)+1 ≥ d(u)+ 1 = d(v)+ 2. Thus, the edge gets added only if label increases by 2. Thus, for each edge, number of times saturating push can occur is O(n). So the total number of saturating pushes is O(nm).

REMARK 12.6 Increase in label of d(u) can make a reverse flow along all arcs (x, u) possible, and not just (v, u); in fact there are at most degree(u) such arcs. Thus, number of saturating pushes are O(nm) and not O(n2).

FACT 12.7 Consider the point in time when the algorithm terminates, i.e., when pushes or relabels can no longer be applied. As excess at s is ∞, excess at s could not have been exhausted. The fact that push/relabels can not be applied means that there is no path from s to t. Thus, Sg , the set of vertices from which t is reachable, and Sg , set of vertices from which s is reachable, form an s − t cut.

Consider an edge (u, v) with u ∈ Sg and v ∈ Sg . As t is reachable from v, there is no excess at v. Moreover, by definition of cut, the edge is not present in residual graph, or in other words, flow in this edge is equal to capacity. By Theorem 12.4, the flow is the maximum possible.