> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vi-graph-algorithms/24.-maximum-flow.md). # 24. Maximum Flow ## Exercises ### 24.1-1 **Available in the latest revision of the IM.** ### 24.1-2 **Available in the latest revision of the IM.** ### 24.1-3 **Available in the latest revision of the IM.** ### 24.1-4 **Available in the latest revision of the IM.** ### 24.1-5 **Available in the latest revision of the IM.** ### 24.1-6 🌟 {% hint style="success" %} Shows how to find the maximum number of paths from $$s$$ to $$t$$, where the paths must be edge-disjoint. {% endhint %} **Available in the latest revision of the IM.** {% hint style="info" %} The solution in the IM relies on Theorem 24.10. {% endhint %} ### 24.1-7 **Available in the latest revision of the IM.** ### 24.2-1 **Available in the latest revision of the IM.** ### 24.2-2 **Available in the latest revision of the IM.** ### 24.2-3 Use the [VisuAlgo](https://visualgo.net/en/maxflow) tool and enter the following 0-indexed graph in edge list format: ``` 6 9 0 1 16 0 2 13 1 3 12 2 1 4 2 4 14 3 2 9 3 5 20 4 3 7 4 5 4 ``` Select the Edmonds-Karp algorithm and watch it running. ### 24.2-4 **Available in the latest revision of the IM.** ### 24.2-5 Make any cut $$(S,T)$$ in the original network $$G$$, where $$S$$ contains all the sources and $$T$$ contains all the sinks. Based on Corollary 24.5, any flow in $$G$$ is bounded from above by the capacity of this cut of $$G$$. Now, create a new cut $$(S',T')$$ in the transformed graph $$G'$$ such that $$S'=S \cup {s}$$ and $$T'=T \cup {t}$$. This cut has a finite value, so any flow in $$G'$$ is also finite. ### 24.2-6 **Available in the latest revision of the IM.** ### 24.2-7 **Available in the latest revision of the IM.** ### 24.2-8 **Available in the latest revision of the IM.** {% hint style="warning" %} The justification given in the IM, that `FORD-FULKERSON` chooses only simple paths, is incorrect. There is nothing explicitly stated in the pseudocode that it considers only such paths. We must demonstrate that, had such a constraint been added, the system would still have functioned correctly.\ \ If an augmenting path $$p$$ in the residual network includes an edge into $$s$$, it must have the structure $$s \leadsto u \to s \leadsto t$$. Pushing $$c$$ units of flow along the first segment ($$s \leadsto u \to s$$) pushes $$c$$ units out of $$s$$ and exactly $$c$$ units back into $$s$$. This subpath forms a cycle whose net effect on the flow out of $$s$$ is zero. Because the path eventually reaches $$t$$, the second segment ($$s \leadsto t$$) must exist in the residual network. If we can push flow along $$s \leadsto u \to s \leadsto t$$, we can achieve the exact same increase in net flow by simply pushing it along the simpler $$s \leadsto t$$ segment. This is why we can redefine the residual network to disallow edges into $$s$$. {% endhint %} ### 24.2-9 **Available in the latest revision of the IM.** ### 24.2-10 **Available in the latest revision of the IM.** ### 24.2-11 🌟 {% hint style="success" %} Shows how to determine the edge connectivity of an undirected graph $$G = (V, E)$$. {% endhint %} **Available in the latest revision of the IM.** ### 24.2-12 **Available in the latest revision of the IM.** ### 24.2-13 🌟 {% hint style="success" %} Shows how to modify the capacities of $$G$$ to create a new flow network $$G'$$ in which any minimum cut in $$G'$$ is a minimum cut with the smallest number of edges in $$G$$. {% endhint %} **Available in the latest revision of the IM.** ### 24.3-1 The algorithm finds the maximum flow in four iterations: 1. The lexicographically smallest path `s -> 1 -> 6 -> t` is found and augmented. The residual network updates by removing these forward edges and adding reverse edges (1-s, 6-1, t-6) with capacity 1. 2. The next smallest path is `s -> 2 -> 8 -> t`. The residual network is updated accordingly. 3. The third path is `s -> 3 -> 7 -> t`. Note that the final edge (7-t) is the only available edge leading to *t*. The residual network is updated. 4. The algorithm attempts to find another path but fails. The final state confirms a maximum flow of 3, which corresponds to the size of the maximum bipartite matching: (1, 6), (2, 8), and (3, 7). ### 24.3-2 **Available in the latest revision of the IM.** ### 24.3-3 **Available in the latest revision of the IM.** ## Problems ### 24-1 Escape problem **Available in the latest revision of the IM.** ### 24-2 Minimum path cover **Available in the latest revision of the IM.** ### 24-3 Hiring consulting experts **Available in the latest revision of the IM.** ### 24-4 Updating maximum flow **Available in the latest revision of the IM.** ### 24-5 Maximum flow by scaling **Available in the latest revision of the IM.** ### 24-6 Widest augmenting path **Available in the latest revision of the IM.** #### Flow conservation in a residual network Part (c) needs additional explanation about why the flow $$f'=f^\*-f$$ satisfies the flow conservation property. To account for antiparallel edges in the residual network $$G\_f$$, flow conservation is proven by looking at the *net flow* between any pair of vertices rather than individual directional edges. When constructing the remaining flow $$f'$$ in the residual network $$G\_f$$, the physical flow placed on the forward residual edges $$(u, v)$$ and backward cancellation edges $$(v, u)$$ is strictly designed so that the net flow of $$f'$$ matches the difference between the optimal flow $$f^\*$$ and the current flow $$f$$. The net flow of $$f'$$ between any two vertices $$u$$ and $$v$$ is established as: $$ f'(u, v) - f'(v, u) = \big( f^*(u, v) - f^*(v, u) \big) - \big( f(u, v) - f(v, u) \big). $$ To prove that $$f'$$ conserves flow at vertex $$u$$ across all of these residual parallel and antiparallel edges, we sum this net flow equation over all vertices $$v \in V$$: $$ \sum\_{v \in V} \big( f'(u, v) - f'(v, u) \big) = \sum\_{v \in V} \left\[ \big( f^*(u, v) - f^*(v, u) \big) - \big( f(u, v) - f(v, u) \big) \right]. $$ We can then distribute the summation to group the terms for $$f^\*$$ and $$f$$: $$ \sum\_{v \in V} \big( f'(u, v) - f'(v, u) \big) = \underbrace{\sum\_{v \in V} \big( f^*(u, v) - f^*(v, u) \big)}*{0} - \underbrace{\sum*{v \in V} \big( f(u, v) - f(v, u) \big)}\_{0}=0. $$ Because $$f^\*$$ is a completely valid flow in the original network, the sum of its net flows at any intermediate node $$u$$ evaluates to exactly 0. Because $$f$$ is also a valid flow, its net flow sum at $$u$$ also evaluates to 0. By framing conservation around net flow instead of strictly unidirectional edge sums, the algebra inherently accounts for how cancellation edges and forward residual edges balance each other out. The net flow entering and leaving $$u$$ for $$f'$$ is precisely 0, meaning flow conservation is perfectly satisfied in $$G\_f$$ regardless of the presence of antiparallel edges. ### 24-7 Global minimum cut #### a. We first need to preprocess the input graph to convert it into a directed version without antiparallel edges (the book explains the whole process). All edges must have capacity of 1. Afterward, we just proceed as described in the text of the exercise. The correctness of this approach follows from the following observations: * A global minimum cut partitions the vertex set $$V$$ into two non-empty sets, $$V\_1$$ and $$V\_2$$. * Because both sets are non-empty, there exists at least one vertex $$u \in V\_1$$ and at least one vertex $$v \in V\_2$$. * By solving the maximum-flow problem for all $$\binom{\vert{}V\vert{}}{2}$$ possible pairs of vertices, you are guaranteed to eventually test a pair $$(u, v)$$ where $$u$$ and $$v$$ lie on opposite sides of the true global minimum cut. * By the max-flow min-cut theorem, the maximum flow between this specific $$u$$ and $$v$$ will equal the capacity of the minimum cut, which in this case is bounded by the global minimum cut. * Therefore, taking the minimum value of the cuts found across all $$\binom{\vert{}V\vert{}}{2}$$ iterations guarantees finding the global minimum cut of the graph. #### b. Any vertex $$u$$ must belong to only one set ($$V\_1$$ or $$V\_2$$). Therefore, we can fix this vertex as a source and examine the remaining vertices as sinks. As in part (a), this will compute the global minimum cut of the graph. The total running time is $$O(V^2E^2)$$ if we emply the Edmonds-Karp algorithm. #### c. * Proving $$\mu(G/(u, v)) \ge \mu(G)$$: When you contract the edge $$(u, v)$$, you merge $$u$$ and $$v$$ into a single vertex. This physically forces $$u$$ and $$v$$ to be on the same side of any subsequent cut. Consequently, any valid cut in the contracted multigraph $$G/(u, v)$$ corresponds exactly to a valid cut in the original multigraph $$G$$ where the edge $$(u, v)$$ does not cross the partition. Because the set of all cuts in $$G/(u, v)$$ is simply a subset of all cuts in $$G$$, the minimum cut value of this restricted subset cannot be smaller than the minimum cut value of the entire set. * Condition for $$\mu(G/(u, v)) > \mu(G)$$: The problem text states to assume that the minimum cut in the multigraph $$G$$ is unique. Under this assumption, the strict inequality occurs if and only if the edge $$(u, v)$$ crosses this unique global minimum cut. If $$(u, v)$$ belongs to the unique minimum cut, contracting it makes that specific cut impossible to form in $$G/(u, v)$$. Since it was the unique minimum, every remaining valid cut in the contracted graph must have a strictly larger capacity, forcing $$\mu(G/(u, v))$$ to be strictly greater than $$\mu(G)$$. #### d. There must be at least one vertex whose degree is at most the average. By selecting it as a sole member of one vertex set, the $$\mu(G)$$ is also bounded from above by this average degree. See [Exercise B.4-1](https://evarga.gitbook.io/sh-intro-to-algs/part-vi-graph-algorithms/pages/ZXxfwYY21Yz9PCv9X7ja#b.4-1) to understand how the formula stated in the book is derived. #### e. $$ \text{Probability} = \frac{\mu(G)}{\vert{}E\vert{}} \le \frac{\frac{2\vert{}E\vert{}}{\vert{}V\vert{}}}{\vert{}E\vert{}} = \frac{2}{\vert{}V\vert{}}. $$ {% hint style="info" %} While part (d) provides the algebraic bound, part (c) provides the operational context for the broader algorithm: as long as you do not pick one of these edges to contract, the original minimum cut is safely preserved in the contracted graph {% endhint %} #### f. To successfully find the global minimum cut, the contraction algorithm must avoid contracting any edge that belongs to the minimum cut throughout its entire execution. Let $$n = \vert{}V\vert{}$$ be the initial number of vertices. The algorithm performs exactly $$n - 2$$ contractions until only 2 vertices remain. * When there are $$k$$ vertices remaining, the result from the previous part establishes that the probability of randomly choosing an edge in the minimum cut is at most $$2/k$$. * Therefore, the probability of *avoiding* the minimum cut at this specific step is at least $$1 - \frac{2}{k} = \frac{k - 2}{k}$$. Because the algorithm must successfully avoid the minimum cut at every single step, we calculate the total probability by multiplying the probabilities of each step from $$k = n$$ down to $$k = 3$$: $$ \begin{align\*} \Pr{c(u, v) = \mu(G)} &\ge \prod\_{k=3}^{n} \frac{k-2}{k} \\ &= \left(\frac{n-2}{n}\right) \left(\frac{n-3}{n-1}\right) \left(\frac{n-4}{n-2}\right) \dots \left(\frac{3}{5}\right) \left(\frac{2}{4}\right) \left(\frac{1}{3}\right) \\ &= \frac{2}{n(n-1)} \\ &=\Omega\left(1/\binom{\vert{}V\vert{}}{2}\right). \end{align\*} $$ #### g. $$ \begin{align\*} \text{Pr(all runs fail)} &\le \left( 1 - \frac{1}{\binom{\vert{}V\vert{}}{2}} \right)^{\binom{\vert{}V\vert{}}{2} \ln \vert{}V\vert{}} \\ &\le \left( e^{-1 / \binom{\vert{}V\vert{}}{2}} \right)^{\binom{\vert{}V\vert{}}{2} \ln \vert{}V\vert{}} && \text{($1 - x \le e^{-x}$)} \\ &= e^{-\ln \vert{}V\vert{}} \\ &= 1 / \vert{}V\vert{}. \end{align\*} $$ Therefore, the probability of success is $$1 - \text{Pr(all runs fail)}$$, which evaluates to a probability of at least $$1 - 1 / \vert{}V\vert{}$$. #### h. Take a look into [Karger's algorithm](https://en.wikipedia.org/wiki/Karger%27s_algorithm) on Wikipedia that also includes the description of the improved Karger–Stein algorithm. #### i. Previously, the proof assumed there was exactly one unique minimum cut $$C$$, and we showed the probability of a single run finding $$C$$ is at least $$1 / \binom{\vert{}V\vert{}}{2}$$. If we remove the uniqueness assumption, suppose the graph has $$k \ge 1$$ distinct minimum cuts ($$C\_1, C\_2, \dots, C\_k$$). The probability of the algorithm returning a *specific* minimum cut $$C\_i$$ remains at least $$1 / \binom{\vert{}V\vert{}}{2}$$. Because a single run of the algorithm will ultimately return exactly one cut, returning $$C\_1$$, returning $$C\_2$$, etc., are mutually exclusive events. Therefore, the probability of returning *any* of the minimum cuts is the sum of their individual probabilities: $$ Pr(\text{finding a min cut}) \ge \sum\_{i=1}^{k} \frac{1}{\binom{\vert{}V\vert{}}{2}} = \frac{k}{\binom{\vert{}V\vert{}}{2}} \ge \frac{1}{\binom{\vert{}V\vert{}}{2}}. $$ Thus, having multiple minimum cuts only strictly increases your chances of finding one, meaning the lower bound of $$1 / \binom{\vert{}V\vert{}}{2}$$ remains completely valid. We can calculate the total running time as follows: * Time per run: As established in part (h), a single run of the contraction algorithm takes $$O(V^2)$$ time. * Number of runs: The algorithm is repeated $$\binom{\vert{}V\vert{}}{2} \ln \vert{}V\vert{}$$ times. Since $$\binom{\vert{}V\vert{}}{2} = \frac{\vert{}V\vert{}(\vert{}V\vert{}-1)}{2} = O(V^2)$$, and natural logarithms differ from base-2 logarithms by only a constant factor, the total number of runs is $$O(V^2 \lg V)$$. * Total time: $$O(V^2) \times O(V^2 \lg V) = O(V^4 \lg V)$$. Using the valid lower bound of $$1 / \binom{\vert{}V\vert{}}{2}$$ for a single run, the math from part (g) applies identically. The probability that all $$\binom{\vert{}V\vert{}}{2} \ln \vert{}V\vert{}$$ independent runs fail to find *any* of the minimum cuts is bounded by: $$ \left( 1 - \frac{1}{\binom{\vert{}V\vert{}}{2}} \right)^{\binom{\vert{}V\vert{}}{2} \ln \vert{}V\vert{}} \le e^{-\ln \vert{}V\vert{}} = \frac{1}{\vert{}V\vert{}}. $$ Since the failure probability is at most $$1 / \vert{}V\vert{}$$, the probability that at least one run successfully returns a global minimum cut is at least $$1 - 1 / \vert{}V\vert{}$$.