AC The Ford-Fulkerson Labeling Algorithm

Section 13.4 The Ford-Fulkerson Labeling Algorithm

In this section, we outline the classic Ford-Fulkerson labeling algorithm for finding a maximum flow in a network. The algorithm begins with a linear order on the vertex set which establishes a notion of precedence. Typically, the first vertex in this linear order is the source while the second is the sink. After that, the vertices can be listed in any order. In this book, we will use the following convention: the vertices will be labeled with capital letters of the English alphabet and the linear order will be \((S,T,A,B,C,D,E,F,G,\dots)\text{,}\) which we will refer to as the pseudo-alphabetic order. Of course, this convention only makes sense for networks with at most \(26\) vertices, but this limitation will not cramp our style. For real world problems, we take comfort in the fact that computers can deal quite easily with integer keys of just about any size.

Before providing a precise description of the algorithm, let’s take a minute to consider a general overview. In carrying out the labeling algorithm, vertices will be classified as either labeled or unlabeled. At first, we will start with only the source being labeled while all other vertices will be unlabeled. By criteria yet to be spelled out, we will systematically consider unlabeled vertices and determine which should be labeled. If we ever label the sink, then we will have discovered an augmenting path, and the flow will be suitably updated. After updating the flow, we start over again with just the source being labeled.

This process will be repeated until (and we will see that this always occurs) we reach a point where the labeling halts with some vertices labeled (one of these is the source) and some vertices unlabeled (one of these is the sink). We will then note that the partition \(V= L\cup U\) into labeled and unlabeled vertices (hence our choice of \(L\) and \(U\) as names) is a cut whose capacity is exactly equal to the value of the current flow. This resolves the debate from earlier in the chapter and says that the maximum flow/minimum cut question is more like antichains and partitioning into chains than clique number and chromatic number. In particular, the labeling algorithm will provide a proof of the following theorem:

Theorem 13.10. The Max Flow–Min Cut Theorem.

Let \(G=(V,E)\) be a network. If \(v_0\) is the maximum value of a flow and \(c_0\) is the minimum capacity \(c_0\) of a cut, then \(v_0=c_0\text{.}\)

We’re now ready to describe the Ford-Fulkerson labeling algorithm in detail.

Algorithm 13.11. Ford-Fulkerson Labeling Algorithm.

Labeling the Vertices: Vertices will be labeled with ordered triples of symbols. Each time we start the labeling process, we begin by labeling the source with the triple \((*,+,\infty)\text{.}\) The rules by which we label vertices will be explicit.
Potential on a Labeled Vertex: Let \(u\) be a labeled vertex. The third coordinate of the label given to \(u\) will be positive real number—although it may be infinite. We call this quantity the potential on \(u\) and denote it by \(p(u)\text{.}\) (The potential will serve as the amount that the flow can be updated by.) Note that the potential on the source is infinite.
First Labeled, First Scanned: The labeling algorithm involves a scan from a labeled vertex \(u\text{.}\) As the vertices are labeled, they determine another linear order. The source will always be the first vertex in this order. After that, the order in which vertices are labeled will change with time. But the important rule is that we scan vertices in the order that they are labeled—until we label the sink. If for example, the initial scan—always done from the source—results in labels being applied to vertices \(D\text{,}\) \(G\) and \(M\text{,}\) then we next scan from vertex \(D\text{.}\) If that scan results in vertices \(B\text{,}\) \(F\text{,}\) and \(Q\) being labeled, then we next scan from \(G\text{,}\) as it was labeled before \(B\text{,}\) even though \(B\) precedes \(G\) in the pseudo-alphabetic order. This aspect of the algorithm results in a breadth-first search of the vertices looking for ways to label previously unlabeled vertices.
Never Relabel a Vertex: Once a vertex is labeled, we do not change its label. We are content to label previously unlabeled vertices—up until the time where we label the sink. Then, after updating the flow and increasing the value, all labels, except of course the special label on the source, are discarded and we start all over again.
Labeling Vertices Using Forward Edges: Suppose we are scanning from a labeled vertex \(u\) with potential \(p(u)>0\text{.}\) From \(u\text{,}\) we consider the unlabeled neighbors of \(u\) in pseudo-alphabetic order. Now suppose that we are looking at a neighbor \(v\) of \(u\) with the edge \((u,v)\) belonging to the network. This means that the edge is directed from \(u\) to \(v\text{.}\) If \(e=(u,v)\) is not full, then we label the vertex \(v\) with the triple \((u,+,p(v))\) where \(p(v)=\min\{p(u),c(e)-\phi(e)\}\text{.}\) We use this definition since the flow cannot be increased by more than the prior potential or the spare capacity on \(e\text{.}\) Note that the potential \(p(v)\) is positive since \(a\) is the minimum of two positive numbers.
Labeling Vertices Using Backward Edges: Now suppose that we are looking at a neighbor \(v\) of \(u\) with the edge \((v,u)\) belonging to the network. This means that the edge is directed from \(v\) to \(u\text{.}\) If \(e=(v,u)\) is used, then we label the vertex \(v\) with the triple \((u,-,p(v))\) where \(p(v)=\min\{p(u),\phi(e)\}\text{.}\) Here \(p(v)\) is defined this way since the flow on \(e\) cannot be decreased by more than \(\phi(e)\) or \(p(u)\text{.}\) Again, note that the potential \(p(v)\) is positive since \(a\) is the minimum of two positive numbers.
What Happens When the Sink is Labeled?: The labeling algorithm halts if the sink is ever labeled. Note that we are always trying our best to label the sink, since in each scan the sink is the very first vertex to be considered. Now suppose that the sink is labeled with the triple \((u,+,a)\text{.}\) Note that the second coordinate on the label must be \(+\) since all edges incident with the sink are oriented towards the sink.

We claim that we can find an augmenting path \(P\) which results in an increased flow with \(\delta=a\text{,}\) the potential on the sink. To see this, we merely back-track. The sink \(T\) got its label from \(u=u_1\text{,}\) \(u_1\) got its label from \(u_2\text{,}\) and so forth. Eventually, we discover a vertex \(u_m\) which got its label from the source. The augmenting path is then

\begin{equation*} P=(S,u_m,u_{m-1},\dots,u_1,T). \end{equation*}

The value of \(\delta\) for this path is the potential \(p(T)\) on the sink since we’ve carefully ensured that \(p(u_m)\geq p(u_{m-1})\geq\cdots\geq p(u_1)\geq p(T)\text{.}\)
And if the Sink is Not Labeled?: On the other hand, suppose we have scanned from every labeled vertex and there are still unlabeled vertices remaining, one of which is the sink. Now we claim victory. To see that we have won, we simply observe that if \(L\) is the set of labeled vertices, and \(U\) is the set of unlabeled vertices, then every edge \(e=(x,y)\) with \(x\in L\) and \(y\in U\) is full, i.e., \(\phi(e)=c(e)\text{.}\) If this were not the case, then \(y\) would qualify for a label with \(x\) as the first coordinate. Also, note that \(\phi(y,x)=0\) for every edge \(e\) with \(x\in L\) and \(y\in U\text{.}\) Regardless, we see that the capacity of the cut \(V=L\cup U\) is exactly equal to the value of the current flow, so we have both a maximum flow and minimum cut providing a certificate of optimality.

You have attempted of activities on this page.