26.4 Push-relabel algorithms

26.4-1

Prove that, after the procedure \(\text{INITIALIZE-PREFLOW}(G, S)\) terminates, we have \(s.e \le -|f^\*|\), where \(f^\*\) is a maximum flow for \(G\).

(Removed)

26.4-2

Show how to implement the generic push-relabel algorithm using \(O(V)\) time per relabel operation, \(O(1)\) time per push, and \(O(1)\) time to select an applicable operation, for a total time of \(O(V^2E)\).

We must select an appropriate data structure to store all the information which will allow us to select a valid operation in constant time. To do this, we will need to maintain a list of overflowing vertices. By Lemma 26.14, a push or a relabel operation always applies to an overflowing vertex. To determine which operation to perform, we need to determine whether \(u.h = v.h + 1\) for some \(v \in N(u)\). We'll do this by maintaining a list \(u.high\) of all neighbors of \(u\) in \(G_f\) which have height greater than or equal to \(u\). We'll update these attributes in the \(\text{PUSH}\) and \(\text{RELABEL}\) functions. It is clear from the pseudocode given for \(\text{PUSH}\) that we can execute it in constant time, provided we have maintain the attributes \(\delta_f(u, v)\), \(u.e\), \(c_f(u, v)\), \((u, v).f\) and \(u.h\). Each time we call \(\text{PUSH}(u, v)\) the result is that \(u\) is no longer overflowing, so we must remove it from the list.

Maintain a pointer \(u.overflow\) to \(u\)'s position in the overflow list. If a vertex \(u\) is not overflowing, set \(u.overflow = \text{NIL}\). Next, check if \(v\) became overflowing. If so, set \(v.overflow\) equal to the head of the overflow list. Since we can update the pointer in constant time and delete from a linked list given a pointer to the element to be deleted in constant time, we can maintain the list in \(O(1)\).

The \(\text{RELABEL}\) operation takes \(O(V)\) because we need to compute the minimum \(v.h\) from among all \((u, v) \in E_f\), and there could be \(|V| - 1\) many such \(v\). We will also need to update \(u.high\) during \(\text{RELABEL}\). When \(\text{RELABEL}(u)\) is called, set \(u.high\) equal to the empty list and for each vertex \(v\) which is adjacent to \(u\), if \(v.h = u.h + 1\), add \(u\) to the list \(v.high\). Since this takes constant time per adjacent vertex we can maintain the attribute in \(O(V)\) per call to relabel.

26.4-3

Prove that the generic push-relabel algorithm spends a total of only \(O(VE)\) time in performing all the \(O(V^2)\) relabel operations.

(Removed)

26.4-4

Suppose that we have found a maximum flow in a flow network \(G = (V, E)\) using a push-relabel algorithm. Give a fast algorithm to find a minimum cut in \(G\).

(Removed)

26.4-5

Give an efficient push-relabel algorithm to find a maximum matching in a bipartite graph. Analyze your algorithm.

First, construct the flow network for the bipartite graph as in the previous section. Then, we relabel everything in \(L\). Then, we push from every vertex in \(L\) to a vertex in \(R\), so long as it is possible.

Keeping track of those that vertices of \(L\) that are still overflowing can be done by a simple bit vector. Then, we relabel everything in R and push to the last vertex. Once these operations have been done, The only possible valid operations are to relabel the vertices of \(L\) that weren't able to find an edge that they could push their flow along, so could possibly have to get a push back from \(R\) to \(L\). This continues until there are no more operations to do. This takes time of \(O(V(E + V))\).

26.4-6

Suppose that all edge capacities in a flow network \(G = (V, E)\) are in the set \(\\{1, 2, \ldots, k\\}\). Analyze the running time of the generic push-relabel algorithm in terms of \(|V|\), \(|E|\), and \(k\). (\(\textit{Hint:}\) How many times can each edge support a nonsaturating push before it becomes saturated?)

The number of relabel operations and saturating pushes is the same as before. An edge can handle at most \(k\) nonsaturating pushes before it becomes saturated, so the number of nonsaturating pushes is at most \(2k|V||E|\). Thus, the total number of basic operations is at most \(2|V|^2 + 2|V||E| + 2k|V||E| = O(kVE)\).

26.4-7

Show that we could change line 6 of \(\text{INITIALIZE-PREFLOW}\) to

C++
1	6 s.h = |G.V| - 2

without affecting the correctness or asymptotic performance of the generic pushrelabel algorithm.

(Removed)

26.4-8

Let \(\delta_f(u, v)\) be the distance (number of edges) from \(u\) to \(v\) in the residual network \(G_f\). Show that the \(\text{GENERIC-PUSH-RELABEL}\) procedure maintains the properties that \(u.h < |V|\) implies \(u.h \le \delta_f(u, t)\) and that \(u.h \ge |V|\) implies \(u.h - |V| \le \delta_f(u, s)\).

We'll prove the claim by induction on the number of push and relabel operations. Initially, we have \(u.h = |V|\) if \(u = s\) and \(0\) otherwise. We have \(s.h - |V| = 0 \le \delta_f(s, s) = 0\) and \(u.h = 0 \le \delta_f(u, t)\) for all \(u \ne s\), so the claim holds prior to the first iteration of the while loop on line 2 of the \(\text{GENERIC-PUSH-RELABEL}\) algorithm.

Suppose that the properties have been maintained thus far. If the next iteration is a nonsaturating push then the properties are maintained because the heights and existence of edges in the residual network are preserved. If it is a saturating push then edge \((u, v)\) is removed from the residual network, which increases both \(\delta_f(u, t)\) and \(\delta_f(u, s)\), so the properties are maintained regardless of the height of \(u\).

Now suppose that the next iteration causes a relabel of vertex \(u\). For all \(v\) such that \((u, v) \in E_f\) we must have \(u.h \le v.h\). Let \(v' = \min\\{v.h \mid (u,v) \in E_f\\}\). There are two cases to consider.

• First, suppose that \(v.h < |V|\). Then after relabeling we have

  \[u.h = 1 + v'.h \le 1 + \min_{(u, v)} \in E_f \delta_f(v, t) = \delta_f(u, t).\]

• Second, suppose that \(v'.h \ge |V|\). Then after relabeling we have

  \[u.h = 1 + v'.h \le 1 + |V| + \min_{(u, v)} \in E_f \delta_f(v, s) = \delta_f(u, s) + |V|,\]

  which implies that \(u.h - |V| \le \delta_f(u, s)\).

Therefore, the \(\text{GENERIC-PUSH-RELABEL}\) procedure maintains the desired properties.

26.4-9 \(\star\)

As in the previous exercise, let \(\delta_f(u, v)\) be the distance from \(u\) to \(v\) in the residual network \(G_f\). Show how to modify the generic push-relabel algorithm to maintain the property that \(u.h < |V|\) implies \(u.h = \delta_f(u, t)\) and that \(u.h \ge |V|\) implies \(u.h - |V| = \delta_f(u, s)\). The total time that your implementation dedicates to maintaining this property should be \(O(VE)\).

What we should do is to, for successive backwards neighborhoods of \(t\), relabel everything in that neighborhood. This will only take at most \(O(VE)\) time (see 26.4-3). This also has the upshot of making it so that once we are done with it, every vertex's height is equal to the quantity \(\delta_f(u, t)\). Then, since we begin with equality, after doing this, the inductive step we had in the solution to the previous exercise shows that this equality is preserved.

26.4-10

Show that the number of nonsaturating pushes executed by the \(\text{GENERIC-PUSH-RELABEL}\) procedure on a flow network \(G = (V, E)\) is at most \(4|V|^2|E|\) for \(|V| \ge 4\).

Each vertex has maximum height \(2|V| - 1\). Since heights don't decrease, and there are \(|V| - 2\) vertices which can be overflowing, the maximum contribution of relabels to \(\Phi\) over all vertices is \((2|V| - 1)(|V| - 2)\). A saturating push from \(u\) to \(v\) increases \(\Phi\) by at most \(v.h \le 2|V| - 1\), and there are at most \(2|V||E|\) saturating pushes, so the total contribution over all saturating pushes to \(\Phi\) is at most \((2|V| - 1)(2|V||E|)\). Since each nonsaturating push decrements \(\Phi\) by at least on and \(\Phi\) must equal zero upon termination, we must have that the number of nonsaturating pushes is at most

Using the fact that \(|E| \ge |V| - 1\) and \(|V| \ge 4\) we can bound the number of saturating pushes by \(4|V|^2|E|\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用