Maximum Flow / Minimum Cut

The maximum flow problem finds the total flow that can be routed through a capacitated network from a given source vertex to a given sink vertex. The minimum cut problem finds a set of edges in the same graph with minimal combined capacity that, when removed, would disconnect the source from the sink. The two problems are related through duality: the maximum flow is equal to the capacity of the minimum cut.

The first algorithm proposed to solve this problem was the Ford-Fulkerson algorithm 1. Goldberg and Tarjan2 later proposed the famous push-relabel algorithm, and more recently, Orlin3 and other authors have proposed polynomial-time algorithms. The maximum flow problem is a special case of the minimum cost flow problem, so it can also be solved efficiently using the network simplex algorithm 4 making a linear programming (LP) solver a suitable approach.

Problem Specification

Let \(G\) be a graph with set of vertices \(V\) and edges \(E\). Each edge \((i,j)\in E\) has capacity \(B_{ij}\in\mathbb{R}\). Given a source vertex \(s\in V\) and a sink vertex \(t\in V\) the two problems can be stated as follows:

• Maximum Flow: Find the flow with maximum value from source to sink such that the flow is capacity feasible.

• Minimum Cut: Find the set of edges which disconnects the source and sink such that the total capacity of the cut is minimised.

Background: Optimization Model

Let us define a set of continuous variables \(x_{ij}\) to represent the amount of non-negative (\(\geq 0\)) flow going through an edge \((i,j) \in E\).

The mathematical formulation for the maximum flow can be stated as:

\[\begin{split}\begin{alignat}{2} \max \quad & \sum_{j \in \delta^+(s)} x_{sj} \\ \mbox{s.t.} \quad & \sum_{j \in \delta^-(i)} x_{ji} = \sum_{j \in \delta^+(i)} x_{ij} & \quad\forall i \in V\setminus\{s,t\} \\ & 0 \leq x_{ij} \le B_{ij} & \forall (i, j) \in E \\ \end{alignat}\end{split}\]

where \(\delta^+(\cdot)\) (\(\delta^-(\cdot)\)) denotes the outgoing (incoming) neighbours of a given vertex.

The objective maximises the total outgoing flow from the source vertex. The first set of constraint ensure flow balance for all vertices. That is, for a given node that is neither the source or the sink, the outgoing flow must be equal to the incoming flow. The last set of constraints ensure non-negativity of the variables and that the capacity of each edge is not exceeded.

The minimum cut problem formulation is the dual of the maximum flow formulation. The minimum cut is found by solving the maximum flow problem and extracting the constraint dual values. Specifically, the edges in the cutset are those whose capacity constraints have non-zero dual values. The graph partitions formed by removing the edges in the cutset can then be round by following the predecessor and successor vertices of these edges.

Code and Inputs

This Mod accepts input graphs of any of the following types:

• pandas: using a pd.DataFrame;

• NetworkX: using a nx.DiGraph or nx.Graph;

• SciPy.sparse: using a sp.sparray matrix.

An example of these inputs with their respective requirements is shown below.

pandasNetworkXscipy.sparse

>>> from gurobi_optimods import datasets
>>> edge_data, _ = datasets.simple_graph_pandas()
>>> edge_data[["capacity"]]
               capacity
source target
0      1              2
       2              2
1      3              1
2      3              1
       4              2
3      5              2
4      5              2

The edge_data DataFrame is indexed by source and target nodes and contains columns labelled capacity with the edge attributes.

Solution

Maximum Flow

Let us use the data to solve the maximum flow problem.

pandasNetworkXscipy.sparse

>>> from gurobi_optimods.max_flow import max_flow
>>> obj, flow = max_flow(edge_data, 0, 5, verbose=False) # Find max-flow between nodes 0 and 5
>>> obj
3.0
>>> flow
source  target
0       1         1.0
        2         2.0
1       3         1.0
2       3         1.0
        4         1.0
3       5         2.0
4       5         1.0
Name: flow, dtype: float64

The max_flow function returns the value of the maximum flow as well as a pd.Series with the flow per edge. Similarly as the input DataFrame the resulting series is indexed by source and target. In this case, the resulting maximum flow has value 3.

The solution for this example is shown in the figure below. The edge labels denote the edge capacity and resulting flow: \(x^*_{ij}/B_{ij}\). All edges in the maximum flow solution carry some flow, totalling at 3.0 at the sink.

Minimum Cut

Let us use the data to solve the minimum cut problem.

pandasNetworkXscipy.sparse

>>> from gurobi_optimods.min_cut import min_cut
>>> res = min_cut(edge_data, 0, 5, verbose=False)
>>> res
MinCutResult(cut_value=3.0, partition=({0, 1}, {2, 3, 4, 5}), cutset={(0, 2), (1, 3)})
>>> res.cut_value
3.0
>>> res.partition
({0, 1}, {2, 3, 4, 5})
>>> res.cutset
{(0, 2), (1, 3)}

The min_cut function returns a MinCutResult which contains the cutset value, the partition of the nodes and the edges in the cutset.

The solution for the minimum cut problem is shown in the figure below. The edges in the cutset are shown in blue (with their capacity values shown), and the nodes in the partitions are shown in blue (nodes 0 and 1) and in green (nodes 2, 3, 4 and 5). The capacity of the minimum cut is \(B_{0,2}+B_{1,3}=2+1=3\) which is also the value of the maximum flow. We can also see that if we remove the blue edges we would be left with a disconnected graph with the two partitions.

1

Lester Randolph Ford and Delbert R Fulkerson. Maximal flow through a network. Canadian journal of Mathematics, 8:399–404, 1956.

2

Andrew V Goldberg and Robert E Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4):921–940, 1988.

3

James B Orlin. Max flows in o(nm) time, or better. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, 765–774. 2013.

4

Cenk Çalışkan. A faster polynomial algorithm for the constrained maximum flow problem. Computers & operations research, 39(11):2634–2641, 2012.