Question

Question: Consider the following simple network with edge capacities as shown.

a) Show that, if the Ford-Fulkerson algorithm is run on this graph, a careless choice of updates might cause it to take 1000iterations. Imagine if the capacities were a million instead of 1000.

We will now find a strategy for choosing paths under which the algorithm is guaranteed to terminate in a reasonable number of iterations.

Consider an arbitrary directed network $\left(G=\left(V,E\right),s,t,\left\{c_e\right\}\right)$in which we want to find the maximum flow.Assume for simplicity that all edge capacities are at least 1, and define the capacity of an s - t path to be the smallest capacity of its constituent edges. The fattest path from s to t is the path with the most capacity.

b) Show that the fattest s - t path in a graph can be computed by a variant of Dijkstra’s algorithm.

c) Show that the maximum flow in Gis the sum of individual flows along at most$\left|E\right|$paths from s to t.

d) Now show that if we always increase flow along the fattest path in the residual graph, then the Ford-Fulkerson algorithm will terminate in at most$\mathit{O}\left(\left|E\right|\log F\right)$ iterations, where F is the size of the maximum flow. (Hint: It might help to recall the proof for the greedy set cover algorithm in Section 5.4.)

In fact, an even simpler rule—finding a path in the residual graph using breadth-first search— guarantees that at$\mathit{O}\left(\left|V\right|.\left|E\right|\right)$most iterations will be needed.

Short answer

(a) It iterates 2000 times.

(b) It can be shown that the fattest path in a graph can be computed by modifying Dijkstra’s algorithm.

(c) It can be shown that maximum flow in G is the sum of individual flows along at most $\left|E\right|$paths from s to t.

(d) Yes, The flow can be increased along the fattest path in at most $O\left(\left|E\right|\log F\right)$iterations.

Step-by-step solution

Explain Integer Linear Program

The principle behind the method is that the transmit flow down one of the pathways from the source (start node) to the sink (end node), as long as there is adequate capacity on all edges of the path. Then we discover a new way, and so on. An augmenting route is one that has available capacity

Step 2:Show that, if the Ford-Fulkerson algorithm run on the given graph.

(a)

The Ford-Fulkerson algorithm is to find the maximum flow by searching for incremental paths in the residual graph. If the incremental path found for the first time is $S\to B\to A\to T$by continuing the routine, then the incremental flow would be $S\to B\to A\to T$. So that only one incremental path with flow 1 is found each time and a total of to iterate 2000 times.

Therefore, the total of 2000 iteration.

Show that the fattest s - t path in a graph can be computed by a variant of Dijkstra’s algorithm.

(b)

The Dijkstra’s algorithm can be used here depending on the fact that if a capacity of the path is $s\to K\to r\to t$is equal to c or greater than c.

Consider that cp(v) be the capacity value of all paths from s to v. Initialize cp(v) to 0 and then the Dijkstra’s algorithm can be modified as follows,

for all edges$\left(u,v\right)\in E:$

$$\begin{gathered} \mathrm{if}cp\left(v\right)<\min \left(cp\left(u\right),c\left(u,v\right)\right) \\ cp\left(v\right)=\min \left(\mathrm{cp}\left(\mathrm{u}\right),\mathrm{c}\left(\mathrm{u},\mathrm{v}\right)\right) \\ \mathrm{K} \end{gathered}$$

Therefore, It has been shown that the fattest s - t path in a graph can be computed by a variant of Dijkstra’s algorithm.

Show that the maximum flow in   is the sum of individual flows along at most   paths from   to  .

(c)

Consider a graph G(V,E), that has a minimum cut, that each cut edge e corresponds to exactly a path $p_e$that is equal to $c\left(e\right)$.The sum of the $p_e$is the maximum flow because the number of cut edges $\left|E\right|$will not exceed the number of paths.

Therefore , it can be seen as the maximum flow that cannot be aggregated by more than $\left|E\right|$edge paths.

Show that at the given condition, the Ford-Fulkerson algorithm will terminate at most O(ElogF) iterations.

(d)

Consider the graph that the graph G(V,E) with the largest flow F, that can be summed up by not more than E paths. Then the flow of the fattest path must not be less than $\frac{F}{\left|E\right|}$. Consider the maximum flow be C co-graph after the $t^{th}$iteration, the relation is obtained as follows,

$c_{t+1}\le -\frac{c_t}{\left|E\right|}$

Therefore, the number of iterations are $O\left(\left|\mathrm{E}\right|\mathrm{logF}\right)$.