# What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am assuming it means a path from s to t with maximum total capacities once you sum the capacities across the path. However, I am not sure what the term bottleneck adds to the definition nor was I sure if that was correct. Is that the correct definition?

• A maximum bottle neck (s-t) path usually refers to a path from s to t that maximizes the capacity of the edge with the smallest capacity on the path (a quick google search could have told you that as well en.wikipedia.org/wiki/Widest_path_problem) – Dennis Kraft Oct 23 '15 at 7:07
• @DennisKraft did google but ignored it cuz of the title Widest path problem seemed weird...guess I should have clicked it... – Charlie Parker Oct 23 '15 at 7:09

While I suspect that the notion of "bottleneck" has been introduced in an earlier lesson, it's all in the document you link.

Page 8:

Edmonds and Karp’s first rule is essentially a greedy algorithm:

Choose the augmenting path with largest bottleneck value.

Page 11:

For any flow network $G$ and any vertices $u$ and $v$, let bottleneck $G(u,v)$ denote the maximum, over all paths $\pi$ in $G$ from $u$ to $v$, of the minimum-capacity edge along $\pi$.

This sentence is a bit hard to parse. Unfolded:

Let $P_G(u,v)$ be the set of all $u$-$v$-paths in $G$, and $E(\pi)$ the set of edges that comprise a path $\pi$ in $G$. Then,

$\qquad\displaystyle G(u,v) = \max_{\pi \in P_G(u,v)} \quad \min_{e \in E(\pi)} c(e)$.

Note that $\min_{e \in E(\pi)} c(e)$ is the bottleneck (capacity) of $\pi$.

So Edmongs-Karp picks the $s$-$t$-path with the largest bottleneck (in the residual network), which means it picks the path it can send the most flow over (while maintaining conservation of flows).