Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is the Ford-Fulkerson method but in which we select a shortest augmenting path (path with fewest no. of edges) each iteration.

Edmonds-Karp method

def edmonds_karp(G): # G = (V, E, l, u, s, t)
	f = zero flow # f(u, v) = 0 for each (u, v) in E
	
	while True:
		G_f = # (1) construct residual network
		p = # (2) find shortest augmenting path in G_f (use BFS)
		if p in None:
			# current flow is optimal
			return f
		
		f = f ^ f_p # (3) path augmentation

Running time of Edmonds-Karp

Each iteration takes $O(m)$ time and there are $O(nm)$ iterations, so total running time is $O(n{m}^2)$. This bound does not depend on values of edge capacities or maximum value of a flow.

The bound $O(nm)$ on number of iterations follows from the claim:

• Let $q$ denote number of iterations in Edmonds-Karp, and let $k_1,k_2,k_3,\dots ,k_q$ denote the lengths of augmenting paths selected in iterations $1,2,3,\dots ,q$. So we have:
  1. $1\le k_1\le k_2\le k_3\le \dots k_q\le n-1$
  2. the same length appears in sequence $⟨k_1,k_2,\dots ,k_q⟩$ at most $m$ times
• This claim implies the number of iterations is $q\le nm$. (we omit the proof)

Other maximum-flow algorithms

Definitely not examined.

Augmenting path algorithms:

• modified Edmonds-Karp $O(n^{2}m)$
• Dinic’s $O(n^3)$
• fastest known “blocking flow” algorithm $O(nm\log n)$

“Preflow-push” algorithms

• generic algorithm $O(n^{2}m)$
• lift-to-front algorithm $O(n^3)$
• if special data structure used: $O(nm\log n)$

Maximum bipartite matching problem

Construct a bipartite graph with nodes $E1,E2,\dots ,Ep$ on one side and nodes $T1,T2,\dots ,Tq$ on the other side. An edge $(T_i,E_j)$ means that task $T_i$ can be done by employee $E_j$.

A matching in a bipartite graph is a subset of edges $M$ such that each node belongs to at most one edge in $M$.

Solve using maximum flow problem

For a given bipartite graph $B$, we construct the following flow network $G$, with all edge capacities equal to $1$: There is a one-to-one correspondence between matchings in $B$ and integral flows in $G$. An edge $(v,u)$ in a given matching corresponds to a path flow of value $1$ from $s$ to $t$ which passes over the edge $(v,u)$.

For a matching $M$ in $B$ and the corresponding integral flow $f$ in $G$, the size of the matching $M$ is equal to the value of flow $f$. Hence, finding a maximum-size matching in $B$ is equivalent to finding a maximum integral flow in $G$

Running time is $O(mn)$ where $m$ and $n$ are nodes and edges in $B$. At most $n$ iterations (since value of a maximum flow in $G$ is at most $n$) and each iteration takes $O(m)$ time.

Example 'resource assignment' problem

Consider the problem where:

• We have employees $E_1,E_2,\dots ,E_p$ and tasks $T_1,T_2,\dots ,T_q$.
• Each employee can do some of the tasks, depending on skills.
• We want to allocate tasks such that:
  • Each employee gets at most one task
  • Each task is given to at most one employee
  • Each employee can only get a task which this employee can do
  • Largest possible number of tasks are allocated

We can model this as the maximum bipartite matching problem.

In our application, a matching is a feasible allocation (each employee gets at most one task, each task given to at most one employee, each employee can only get a task which the employee can do).

Hence, maximising the number of allocated tasks is equivalent to finding corresponding bipartite graph matching of the maximum size.

Minimum flow problem

In the minimum flow problem, we want to send the minimum amount of flow from the source to the sink, satisfying upper and lower bounds on edge flows.

The input is a flow network $G=(V,E,l,u,s,t)$ where:

• $V$ is a set of $n$ nodes
• $E$ is a set of $m$ directed edges
• For each $(v,w)\in E$, $0\le l(v,w)\le u(v,w)$ are the lower and upper bounds on the flow of the given edge.
• Two distinguished vertices: source $s$ and sink $t$.
• As before, assume if $(v,w)$ is an edge in $G$, then $(w,v)$ is not an edge.

A feasible flow from $s$ to $t$ is a function $f:\to R$ on the edges, which satisfies the flow conservation constraints at all vertices other than $s$ and $t$, and the lower and upper capacity bounds: $l(v,w)\le f(v,w)\le u(v,w)$

Algorithm

A minimum flow can be computed using 2 steps:

1. Compute a feasible flow $f$, that is, a flow which satisfies all lower and upper bounds on flows of edges.

2. In residual network $G_f$, compute maximum flow from $t$ to $s$. (we want to send back from $t$ to $s$ any ‘excess’ flow)

   For an edge $(v,w)$,

   • Where $l(v,w)\le f(v,w)\le u(v,w)$
   • We have residual capacities: $c_f(v,w)=u(v,w)-f(v,w)$ $c_f(w,v)=f(v,w)-l(v,w)$

   Visually:

   With this definition of residual capacities, the feasibility of the current flow will be maintained: flow on each edge will remain between the lower and upper bounds.

The final flow, interpreted in original network $G$ is a minimum $s-t$ flow.

Each of the two steps can be completed using a maximum flow algorithm.

For the following graph, interpret $(x,y)$ as lower and upper bounds, and $(x)$ as upper bound with lower bound $=0$.

For each edge $(v,w)$ with positive lower bound $l(v,w)$, we send $l(u,w)$ units of flow along these edges, creating supply and demand at various vertices. We consider $s$ and $t$ to have unlimited supply and demand.

Find a feasible flow which satisfies the supplies and demands at all vertices other than $s$ and $t$.

We add a new source (with edges to supply vertices) and a new sink (with edges from demand vertices) and use a maximum-flow algorithm to find a flow which saturates all added edges adjacent to vertices other than $s$ and $t$.

If there is no flow which saturates all added edges adjacent to supply / demand vertices (other than $s$ and $t$) then there is no feasible flow in original network.

If a feasible flow $f$ has been found, then construct the residual network (of computed feasible flow) and compute a maximum flow in this network from $t$ to $s$.

This computation returns back to $s$ as much flow as possible, while keeping the flow feasible. That way, when no more flow can be returned to $s$, the final flow is a minimum feasible flow.

slides 18

Explanation of why algorithm works

• In the residual network of the final flow $f$, there is no augmenting path from $t$ to $s$.
• This means there is a cut $(S,T)$ with no residual edges from $T$ to $S$.
• For this cut $(S,T)$:
  • For each edge $(v,w)$ from $S$ to $T$, $f(v,w)=l(v,w)$.
  • For each edge $(x,y)$ from $T$ to $S$, $l(v,w)=f(v,w)$ (mistake in slides?).
• Value of the flow is equal to the net flow across cut $(S,T)$ which is equal to: $|f|=f(S,T)={\sum }_{(v,w)\in E:v\in S,w\in T}l(v,w)-{\sum }_{(x,y)\in E:x\in T,y\in S}u(x,y)$
• Value of any feasible flow is at least right-hand side value above.
• We conclude that the computed flow is a minimum feasible flow in the input network.

Example 'worker assignment' problem