Graph Theory – Network Flow

Resources

• Slides

Thera are three main problem types of network flow problems:

• Minimum Cost Flow Problem
• Minimum Spending Tree Problem
• Maximum Flow Problem

Directed Graph

We’re using regular weighted directed graphs to solve network flow problems, for example flight routes or supply chains. A directed graph $G=(V,A,c)$ consists of:

• A set of nodes (vertices) $V$.
• A set of arcs (directed edges) $A$, where each arc is defined by a start node $i$ and terminal node $j$. An edge is undirected, meaning travel is possible in both directions, an arc is directed.
• For each arc or edge, a cost (weight) $c_{i,j}$. The weight may be positive, zero, or negative.

Minimum Cost Flow Problem

The minimum cost flow problem is to find the cheapest way of sending a certain amount of flow through a network from supply nodes to demand nodes, while respecting capacity constraints on the arcs. On top of the directed graph $G=(V,A,c)$, we define:

• A net flow ($outflow-inflow$) for each node, $f_J\in \mathbb{R}$, where $f_J>0$:
  • $f_J>0$: supply node (source)
  • $f_J<0$: demand node (sink)
  • $f_J=0$: transshipment node (intermediate node)
• On each arc, a variable cost $c_{i,j}$ per transported unit, a maximum flow ${\kappa }_{i,j}$ and a minimum flow ${\lambda }_{i,j}$.

We want to determine the flow $x_{i,j}$ on each arc $(i,j)\in A$ such that supply nodes serve the demand nodes at minimum cost while respecting the flow capacity constraints.

Transportation Problem

A special case of the minimum cost flow problem , where supply nodes have a certain supply capacity and demand nodes have a certain demand requirement. The goal is to minimize transportation costs while satisfying supply and demand constraints.
An example for this is mapping study abroad requests to available slots at partner universities.

A cost matrix defines the cost of transporting goods from each supply node to each demand node. The problem can be solved using linear programming techniques.

Assignment Problem

A further constrained instance of the transportation problem. Here, each supply node can supply exactly one unit, and each demand node requires exactly one unit. The goal is to minimize the total assignment cost. Therefore, decisions are binary and the cost matrix is square.

Shortest Path Problem

Another special case of the minimum cost flow problem, where the objective is to find the shortest path from one source node to one destination node in a weighted directed graph. Here, each arc’s weight could be something like time, distance or environmental impact, and the goal is to minimize the total cost of traveling from the source to the destination. Decision variables are binary, indicating whether an arc is included in the path or not.

Solving the shortest path is explained in Path-Solvers.

Linear Program Representation

The objective is to minimize the cost of transporting flow through the network:

$$\begin{array}{rl}\min z=\sum _{(i,k)\in A}{c}_{i,j}\cdot x_{i,j}& \\ & \\ s.t.-\sum _{(h,i)\in A}{x}_{h,i}+\sum _{(i,j)\in A}{x}_{i,j}=f_i& \forall i\in V\text{(net flow)}\\ & \\ x_{i,j}\ge {\lambda }_{i,j}& \forall (i,j)\in A\text{(minimum flow)}\\ & \\ x_{i,j}\le {\kappa }_{i,j}& \forall (i,j)\in A\text{(maximum flow)}\\ & \\ x_{i,j}\ge 0& \forall (i,j)\in A\text{(non-negativity)}\end{array}$$

Path Solvers

Dijkstra’s Algorithm

Dijkstra’s algorithm is a popular method for finding the shortest path from a source node to all other nodes in a weighted directed graph with non-negative edge weights. It works by iteratively selecting the node with the smallest tentative distance from the source and updating the distances of its neighbors. We use these data structures:

• $d[1,\dots ,n]$: array of distances from node $s$ to each node; $d[i]$ is the current shortest distance from $s$ to $i$
• $p[1,\dots ,n]$: array to store the predecessor of each node in the shortest path; $p[i]$ is the predecessor of node $i$ on the shortest path from $s$
• $M$: set of “marked” nodes whose shortest distance from $s$ is known; a node is added when a path from $s$ has been found and removed when the shortest path from $s$ has been finalized.

Initialization
$d$ is initialized with infinity for all nodes except the source node $s$, which is set to 0. The predecessor array $p$ is initialized with null values. M is initialized with the starting node only.

Iteration
While $M$ is not empty, the node with the smallest distance in $d$ is selected from $M$ and removed from it. For each neighbor (nodes with an arc from the current node), we check if the distance to that neighbor can be improved by going through the current node. If so, we update the distance $d$ and set the predecessor $p$ accordingly. The neighbor is then added to $M$ if it is not already present.

Termination
Once all nodes have been processed (i.e., $M$ is empty), the algorithm terminates. The array $d$ contains the shortest distances from the source node to all other nodes, and the array $p$ can be used to reconstruct the shortest paths. Therefore, the shortest path from the source to any node can be found by backtracking through the predecessor array $p$ starting from the target node.

If only the shortest path to a specific target node $t$ is needed, the algorithm can terminate early once $t$ is removed from $M$.

Floyd-Warshall Algorithm

Contrary to the Dijkstra’s algorithm, the Floyd-Warshall algorithm can handle negative edge weights and finds the shortest paths between all pairs of nodes in a weighted directed graph. It uses dynamic programming to iteratively improve the estimates of the shortest paths by considering intermediate nodes.

It uses two n x n matrices:

• $d[1,\dots ,n][1,\dots ,n]$: distance matrix where $d[i][j]$ represents the shortest distance from node $i$ to node $j$.
• $p[1,\dots ,n][1,\dots ,n]$: predecessor matrix where $p[i][j]$ stores the predecessor of node $j$ on the shortest path from node $i$.

Initialization
$d$ is initialized such that $d[i][j]$ is the weight of the edge from node $i$ to node $j$ if it exists, and infinity otherwise. The diagonal elements $d[i][i]$ are 0 (distance to self). The predecessor matrix $p$ is initialized such that $p[i][j]=i$ if there is an edge from $i$ to $j$, and null otherwise.

Iteration
For each node $k$ in the graph, we consider it as an intermediate node and update the distance matrix $d$ by checking if the path from any neighboring node $i$ to another neighboring node $j$ through $k$ is shorter than the current known distance. If it is, we update $d[i][j]$ to $d[i][k]+d[k][j]$ and set $p[i][j]$ to $p[k][j]$.

Nodes can be selected in any order. The iterations continue until all nodes have been considered as intermediate nodes.

Minimum Spending Tree Problem

The minimum spanning tree problem is to find a subset of edges in an undirected weighted graph that connects all the nodes together without any cycles and with the minimum possible total edge weight. This is used for example in designing cost-efficient networks like electricity or communication networks.

Tree

A connected graph (graph where all nodes are connected) with no cycles. A tree with $n$ nodes has exactly $n-1$ edges. Nodes without children are called leaves. The root is the topmost node in a tree.

Like other problems, the minimum spending tree problem can be formulated as a mixed integer linear program. However, this is inefficient, and irrelevant for this course.

Kruskal’s Algorithm

Initialization
First, all edges are sorted in increasing order based on their weights. If two edges have the same weight, they are ordered by their start and end nodes.

Iteration
Starting with an empty tree, we iterate through the sorted edges and add each edge to the tree if it does not create a cycle. This is typically done using a union-find data structure to efficiently check for cycles. If adding an edge would create a cycle, it is skipped.

The process continues until we have added $n-1$ edges to the tree, where $n$ is the number of nodes in the graph. Finally, the weights of the edges in the minimum spanning tree are summed to get the total cost.

Table Format

When performed manually, Kruskal’s algorithm can be organized in a table format:

Maximum Flow Problem

The maximum flow problem is to find the maximum possible flow from a source node to a sink node in a directed graph, while respecting the capacity constraints on the arcs. This is used in various applications, such as network routing, supply chain management, and project scheduling.

Linear Program Representation

The objective is to maximize the flow from the source node $s$ to the sink node $t$, while respecting the flow conservation and capacity constraints:

$$\begin{array}{rl}\max z=\sum _{(s,j)\in A}{x}_{s,j}-\sum _{(i,s)\in A}{x}_{i,s}& \\ & \\ s.t.-\sum _{(h,i)\in A}{x}_{h,i}+\sum _{(i,j)\in A}{x}_{i,j}=0& \forall i\in V\setminus \{s,t\}\text{(flow conservation)}\\ & \\ x_{i,j}\le {\kappa }_{i,j}& \forall (i,j)\in A\text{(capacity constraint)}\\ & \\ x_{i,j}\ge 0& \forall (i,j)\in A\text{(non-negativity)}\end{array}$$

Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm is a method for computing the maximum flow in a flow network. It works by repeatedly finding augmenting paths from the source to the sink and increasing the flow along these paths until no more augmenting paths can be found.

Augmenting Path

A path that is either:

• Non-full forward edges (edges where the current flow is less than the capacity).
• Non-empty backward edges (edges where the current flow is greater than zero, allowing flow to be reduced).

Initialization
Start with an initial flow of 0 on all edges in the network.

Iteration
In each iteration, the algorithm looks for an augmenting path: a forward path that still has capacity, or a backward path where capacity can be reduced. This can be done using depth-first search (DFS) or breadth-first search (BFS).

Once an augmenting path is found, the algorithm determines the maximum amount of flow that can be added along this path (the bottleneck capacity). This is the minimum residual capacity of the edges in the path. The flow is then updated by increasing the flow on the forward edges and decreasing it on the backward edges (and forward edges in the residual graph) along the path.

The process continues until no more augmenting paths can be found from the source to the sink. At this point, the flow value represents the maximum flow in the network.

Table Format

When performed manually, the Ford-Fulkerson algorithm can be organized in a table format:

Minimum Cut Problem

A cut divides a set of nodes into two subsets, such that one subset contains the source node and the other subset contains the sink node. The minimum cut problem is to find the cut with the smallest total capacity of edges crossing the cut, which represents the bottleneck in the network. In other words, it identifies the edges that, if removed, would disconnect the source from the sink with the least total capacity.

Capacity of a Cut

A cut’s capacity is the sum of the capacities ${\kappa }_{i,j}$ of all edges $(i,j)$ that cross from the source side to the sink side of the cut, minus the sum of the capacities of edges crossing back from the sink side to the source side.

Relation to Maximum Flow Problem

The minimum cut problem is the dual problem to the maximum flow problem. It seeks to find the minimum capacity that, when removed, would disconnect the source from the sink in a flow network. The value of the maximum flow is equal to the capacity of the minimum cut, as stated by the max-flow min-cut theorem.

• Max Flow: Calculating the highest rate at which material can move through the network from source to sink.
• Min Cut: Finding the bottleneck in the system—the set of edges with the smallest total capacity that, if removed, would completely disconnect the source from the sink.

Therefore, the duality properties (weak and strong) apply, and $f_{max}=C_{min}$.