# Edmonds-Karp

## General Information

Algorithmic problem: Max-flow problems (standard version)

Algorithm : This is a specialization of Ford-Fulkerson: Among all flow-augmenting paths $(s,t)$-paths, always choose one with smallest number of arcs. Consequently, a BFS is applied to find the path.

## Abstract View

Invariant: identical to the invariant of Ford-Fulkerson.

Notation: For an $(s,t)$-flow, let $A_f$ denote the set of all arcs that belong to at least one flow-augmenting $(s,t)$-path with smallest number of arcs.

Variant:

1. The smallest number of arcs on any flow-aumenting $(s,t)$-path increases (non-strictly) monotonously.
2. Whenever that number does not increase in an iteration, the size of $A_f$ decreases in that iteration.

Break condition: There is no flow-augumenting path.

## Correctness

The correctness proof of Ford-Fulkerson proves the invariant. So, we have to show the variant. In the following, we focus on the residual network $(G_f,u_f)$.

Let $p$ be the flow-augmenting path in the current iteration, and let $k$ be the number of arcs on $p$; in other words, the minimum number of arcs of a flow-augmenting $(s,t)$-path with respect to the current flow. At least one arc of $p$ will be saturated in this iteration and, thus, leave the residual network. Therefore, it remains to show that augmenting the flow along $p$ according to Ford-Fulkerson does not create new flow-augmenting paths of length $k$ or less than $k$.

A new flow-augmenting $(s,t)$-path can only be created if a new arc enters the residual network. This must be an arc $(w,v)$ such that $(v,w)$ is an arc of $p$.

Suppose a new flow-augmenting path $p'$ has been created. We have to show that $p'$ has more than $k$ arcs. Then $p'$ contains $r\geq 1$ arcs as specified in the last paragraph (that is, arcs opposite to arcs on $p$). Let $(w_1,v_1),\ldots,(w_r,v_r)$ denote these arcs, in the order in which they appear on $p'$ (not necessarily the order in which the opposite arcs appear on $p$). For notational convenience, let $v_0:=s$ and $w_{r+1}:=t$.

For $i\in\{0,\ldots,r\}$, let $p_i$ denote the subpath of $p'$ from $v_i$ to $w_{i+1}$. Now, for all paths $p_i$ such that $w_{i+1}$ appears after $v_i$ on $p$, the specific choice of $p$ to have a minimum number of arcs implies that $p_i$ does not have fewer arcs than the subpath of $p$ from $v_i$ to $w_{i+1}$. For the other subpaths $p_i$, it suffices to note the trivial fact that the number of arcs on $p_i$ is not negative. Note that for each arc $a$ on $p$, there is at least one $i\in\{1,\ldots,r\}$ such that $v_i$ precedes $a$ on $p$ and $w_{i+1}$ succeeds $a$ on $p$. So, summing up the numbers of arcs on all $p_i$ and adding the number $r$ of arcs $(w_i,v_i)$ to get the number of arcs on $p'$ proves the claim.

## Complexity

Statement: In any case (even if the upper bounds are not integral), the asymptotic complexity is in $\mathcal{O}(nm^2)$ in the worst case, where $n=|V|$ and $m=|A|$.

Proof: The variant implies that the smallest number of arcs on a flow-augmenting path strictly increases after at most $m$ iterations. This number is positive, but cannot be larger than $n-1$. Hence, the total number of iterations is in $\mathcal{O}(nm)$. The claim then follows from the fact that the complexity of an iteration is linear in the number of arcs.

Remark: The number of nodes is irrelevant for the complexity of an iteration because at most $m$ nodes are reachable from $s$ (not including $s$ itself).