Network Flow

This note is part of my learning notes on Data Structures & Algorithms.

---

Network Flow

Network flow algorithms are used to find the flow with maximum value (maximum flow) in a network, which can be modeled as a graph with nodes and edges representing flow capacities between nodes.

A flow network is a connected, directed graph $G= (V,E)$.

• Each edge $(u,v) \in E$ has a non-negative, integer capacity $c(u,v)$
• Two distinguished vertices
  • A single source $s \in V$
  • A single sink $t \in V$
• No edge enters the source and no edge leaves the sink
• No self-loop edges are allowed
• A flow in G is a function $f: V \times V \rightarrow \real$

Definition of a Flow

The value of a flow $f$, is denoted by $|f|$ , is given by

$$\begin{aligned} |f| &= \sum_{v \in V} f(s,v) \\ &= f(s,V ) \end{aligned}$$

1. Capacity constraint

flow $\leq$ capacity

$$\text{ For all } u,v \in V, 0 \leq f(u,v) \leq c(u,v)$$

2. Flow Conservation

number of flow into the node = number of flow out of the node (nodes that are not $s$ or $t$ )

$$\begin{aligned} &\text{ For all } u \in V - \{s,t\}, \\ &\sum_{v \in V} f(u,v)= \sum_{v \in V} f(v,u) \end{aligned}$$

3. Skew Symmetry

$$\text{ For all } u,v \in V, f(u,v) = -f(v,u)$$

4. Simple Properties of Flow

• $f(X,X)=0$ (because no self-loop nodes)
• $f(X,Y)= - f(Y,X)$
• $f(X \cup Y,Z) = f(X,Z) + f(Y,Z)$, if $X \cap Y=\emptyset$

Theorem

The value of a flow pushed out from the source, eventually goes into the sink.

$$|f| = f(V,t)$$

---

Cuts

A cut $(S,T)$ of a flow network $G=(V,E)$ is a partition of $V$ such that it creates two disjoint set of vertices: $s \in S$ and $t \in T$. $S$ is the set that includes the source node, while $T$ is the set that includes the sink node. The only rule is that the source and the sink cannot be in the same set.

Capacity of a cut $(S,T)$ is $c(S,T)$.

If $f$ is a flow on $G$, then the flow across the cut is $f(S,T)$.

The flow across the cut is as the sum of the flows corresponding to each pair of vertices, such that the source vertex is part of $S$ and the destination vertex is part of $T$.

Lemma

Doesn’t matter what cut you choose, you have a flow on the network. The flow on the network is going to be equal to the flow on the cut.

For any flow $f$ and any cut $(S,T)$, we have

$$|f| = f(S,T)$$

Theorem (Upper Bound of Maximum Flow Value)

The value of any flow is bounded above by the capacity of a cut.

---

Max-Flow Min-Cut Theorem

In this theorem, the following are equivalent:

1. $|f| = c(S,T)$ for some cut $(S,T)$
2. $f$ is a maximum flow
3. $f$ admits no augmenting paths

This theorem states that in any flow network, the maximum amount of flow passing from the source node to the sink node is equal to the minimum capacity of a cut (partitioning the nodes into two sets) in the network.

---

Residual Graph

Residual capacity of a directed edge is its capacity minus its flow. We can create a residual graph from all these types of edges, which has the same vertices and edges, but use the residual capacity as its new capacity.

Let $f$ be a flow on $G=(V,E)$. The residual graph $G_f(V, E_f)$ is the graph with strictly positive residual capacities $c_f(u,v) = c(u,v) - f(u,v) > 0$

• Forward edges: For each edge $e=(u,v)$ of $G$ for which $f(e) < c(e)$, include an edge $e'=(u,v)$ in $G_f$ with capacity $c(e) - f(e)$ .
• Backward edges: For each edge $e=(u,v)$ in $G$ with $f(e) >0$ , we include an edge $e'=(v,u)$ in $G_f$ with capacity $f(e)$.
• If $f(e) < c_e$, add edge $e$ to $G_f$ with capacity $c_e - f(e)$ . (remaining capacity left)
• If $f(u,v)> 0$ , add reverse edge $(v,u)$ with capacity $f(e)$. (can erase up to f(e) capacity)

Edges in $E_f$ admit more flow.

---

Augmenting Path

An augmenting path is a simple path from source to sink in the residual graph, which do not include any cycles and that pass only through positive weighted edges (residual capacity is positive). Any path from $s$ to $t$ in $G_f$ is an augmenting path in $G$ with respect to $f$. The flow value can be increased along an augmenting path $p$ by $c_f(p) = min_{(u,v) \in p} \{ c_f (u,v) \}$

---

Maximum Bipartite Matching

A bipartite graph $G=(V,E)$ is a graph in which the vertex set $V$ can be divided into two disjoint subsets $X$ and $Y$ such that every edge $e \in E$ has one point in $X$ and the other end point in $Y$.

A maximum matching is a matching that contains the largest possible number of edges. Every maximum matching is a maximal matching.

Maximum bipartite matching deals with finding the maximum number of edges that can be added to a bipartite graph such that no two edges share a common endpoint.

Given a bipartite graph $G=(V,E)$ , find an $S \subseteq A \times B$ that is matching and is as large as possible. $S$ is perfect matching if every vertex is matched.

---

Example: Ford-Fulkerson Algorithm

Ford-Fulkerson algorithm is used to solve the maximum flow problem. It iteratively finds augmenting paths from the source to the sink and increases the flow along these paths until no more augmenting paths exist. The maximum flow is reached when there are no more augmenting paths.

Algorithm:

1. set the flow of each edge to zero
2. look for an augmenting path from $s$ to $t$
3. while there is such an augmenting path that runs along edges with positive residual capacity
   • do augment $f$ by $c_f(p)$

Pseudocode:

flow = 0
for each edge (u, v) in G:
    flow(u, v) = 0
while there is a path, p, from s -> t in residual network G_f:
    residual_capacity(p) = min(residual_capacity(u, v) in p)
    flow = flow + residual_capacity(p)
    for each edge (u, v) in p:
        if (u, v) is a forward edge:
            flow(u, v) = flow(u, v) + residual_capacity(p)
        else:
            flow(u, v) = flow(u, v) - residual_capacity(p)
return flow

Running Time

The algorithm terminates in $C$ iterations of the while loop.

$$C = \sum_{e \text{ leaving } s} c_e$$

If $G$ has $m$ edges, $G_f$ has $\leq 2m$ edges. We find a path from source to sink node in $G_f$ with $O(m+n)$ time with depth-first search or breadth-first search.

Since $m \geq \frac{n}{2}$ (every node is adjacent to some edge), $O(m+n) = O(m)$

Hence, the running time for Ford-Fulkerson algorithm to find max flow is

$$\begin{aligned} T(n) &= O(mC) \\ &= O ( M * F_{max} ) \\ &= O(|E| * F_{max}) \end{aligned}$$

• where $F_{max}$ is the value of the maximum flow.

---

Example: Edmonds-Karp Algorithm

Edmonds-Karp algorithm is a variation of the Ford-Fulkerson algorithm. It is also used to solve the max-flow min-cut problem.

Ford-Fulkerson algorithm VS Edmonds-Karp algorithm
FF algorithm doesn’t specify how augmenting paths are found (but it mostly uses depth-first search); while EK algorithm clearly states that they are found using breadth-first search.
FF algorithm finds any augmenting path until there are none left, while EK finds ‘good’ augmenting paths and shortest edges to improve running time.

Algorithm

Pseudocode

def EdmondsKarp(E, C, s, t):
    n = len(C)
    flow = 0
    F = [[0 for y in range(n)] for x in range(n)]
    while True:
        P = [-1 for x in range(n)]
        P[s] = -2
        M = [0 for x in range(n)]
        M[s] = decimal.Decimal('Infinity')
        BFSq = []
        BFSq.append(s)
        pathFlow, P = BFSEK(E, C, s, t, F, P, M, BFSq)
        if pathFlow == 0:
            break
        flow = flow + pathFlow
        v = t
        while v != s:
            u = P[v]
            F[u][v] = F[u][v] + pathFlow
            F[v][u] = F[v][u] - pathFlow
            v = u
    return flow

def BFSEK(E, C, s, t, F, P, M, BFSq):
    while (len(BFSq) > 0):
        u = BFSq.pop(0)
        for v in E[u]:
            if C[u][v] - F[u][v] > 0 and P[v] == -1:
                P[v] = u
                M[v] = min(M[u], C[u][v] - F[u][v])
                if v != t:
                    BFSq.append(v)
                else:
                    return M[t], P
    return 0, P

Running Time

Each iterations of Edmonds-Karp runs in $O(|E|)$ time, and that there are at most $|V|$. So for $|E|$ iterations, the running time is

$$T(n) = O(VE^2)$$

Space complexity is $O(E+V)$.

---

Blocking Flow

A blocking flow in a flow network $G'$ is a flow that saturates at least one edge in every $s-t$ path in $G'$ . It uses all the available capacity of every edge in the network. In other words, a blocking flow is a maximum flow that cannot be increased any further.

Every maximum flow is a blocking flow, but the reverse is not true!

---

Level Graph

A level graph is a special type of graph used to represent a network flow problem during the execution of Dinic’s algorithm. It is one where value of each node is its shortest distance from source, and is created by iteratively assigning levels to nodes in the network.

How to construct a level graph:

1. Initialize all nodes to level $0$
2. If an augmenting path is found, the nodes in the path are assigned levels incrementally. The source node has level 1, and the sink node has the highest level.
3. For every node with level k, all the edges leaving the node with level k are considered to have capacity remaining equal to the difference between the current level of the node and the level of the source node (k-1).

---

Example: Dinic’s Algorithm

Dinic’s Algorithm: is a faster way to calculate maximum flow over the networks. It includes construction of level graphs and residual graphs and finding of augmenting paths along with blocking flow.

Dinic’s Algorithm VS Edmonds Karp Algorithm
Dinic’s algorithm is based on depth-first search, and uses level graphs, while EK algorithm is based on breadth-first search and using augmenting paths.

check if more flow is possible and to construct level graph. In level graph, we assign levels to all nodes, level of a node is shortest distance (in terms of number of edges) of the node from source. Once level graph is constructed, we send multiple flows using this level graph.

Algorithm

1. Create the level graph by performing breadth-first search from the source vertex
2. Locate blocking flows
3. Update the network flow

Pseudocode

function: DinicMaxFlow(Graph G,Node S,Node T):
    Initialize flow in all edges to 0, F = 0
    Construct level graph
    while (there exists an augmenting path in level graph):
        find blocking flow f in level graph
        F = F + f
        Update level graph
    return F

Running Time

$$T(n) = O(EV^2)$$

Space complexity is $O(V+E)$, in which $O(V)$ to store the level array and $O(E)$ to store the graph’s adjacency list.

---

References

• MIT 6.046J Spring 2015: Network flow
• MIT 6.046J Spring 2012: Max-Flow Min-Cut
• Lecture 13. Incremental Improvement
• CMSC 451: Network Flows
• CMSC 451: Maximum Bipartite Matching
• HackerEarth: Maximum Flow Problem
• Baeldung: Dinic’s Algorithm
• CP Algorithms: Edmonds-Karp Algorithm
• Brilliant: Edmonds Karp Algorithm
• 知乎