Minimum Cut and Maximum Flow¶

Ford-Fulkerson Algorithm for Maximum Flow¶

We attempt to find an augmenting path from the source to the sink and use it to add one unit to the flow. We repeat this process until no augmenting path remains. The resulting flow will have a corresponding cut with equal capacity. Since we know all cuts are greater than or equal to all flows, the flow we have found is guaranteed to be the maximum flow.

The following code snippet implements this algorithm. To simplify the process, instead of separately checking forward and backward edges when finding paths, we create a reverse edge with capacity 0 for every original edge. Whenever flow is sent through an edge, we reduce its capacity and increase the capacity of its corresponding reverse edge.

 1def ford_fulkerson(graph, source, sink):
 2    # Create reversed edges with 0 capacity
 3    for u in graph:
 4        for v, capacity in graph[u].items():
 5            if v not in graph:
 6                graph[v] = {}
 7            graph[v][u] = 0
 8
 9    max_flow = 0
10    path = bfs(graph, source, sink)
11
12    while path:
13        # Find minimum residual capacity in the path
14        flow = min(graph[u][v] for u, v in path)
15        for u, v in path:
16            graph[u][v] -= flow
17            graph[v][u] += flow
18        max_flow += flow
19        path = bfs(graph, source, sink)
20    return max_flow

int cnt, head[M], pre[M], cap[M], to[M], from[M];
int n,m;

void add(int u, int v, int w){
    // ezafe kardane yale asli
    from[cnt] = u;
    to[cnt] = v;
    pre[cnt] = head[u];
    cap[cnt] = w;
    head[u] = cnt++;
    // ezafe kardane yale dogaan
    from[cnt] = v;
    to[cnt] = u;
    pre[cnt] = head[v];
    cap[cnt] = 0;
    head[v] = cnt++;
}

int tnod = 0;
bitset <M> mark;

// say mikonim ke masir afzaayesh dahande peydaa konim
int dfs(int u, int mn){
    mark[u] = 1;
    if(u == tnod)return mn;
    // yal haye ras u dar yek link list rikhte shode and.
    for (int i = head[u]; i != -1; i = pre[i]){
        // agar yale hadaf zarfiat nadasht bikhiaale aan mishavim
        if (cap[i] == 0 || mark[to[i]]) continue;
        // say mikonim ke jaryani be maghsad peyda konim
        int s = dfs(to[i], min(mn,cap[i]));
        // agar s = 0 nabashad, masir afzayesh dahande i vojood darad ke
        // kam zarfiat tarin yale aan s vahed zarfiat darad
        if (s){
            // az zarfiate yal s vahed kam mikonim
            cap[i] -= s;
            // be zarfiate yaale dogan s vahed ezafe mikonim
            cap[i^1] += s;
            // elam mikonim ke masir s vahedi peyda shode ast
            return s;
        }
    }
    // masiri peyda nakardim
    return 0;
}

int maxflow(){
    int flow = 0;
    while(1){
        mark &= 0;
        int s = dfs(0, inf);
        // agar masiri peyda nashode bood flow = maxflow
        if (!s) return flow;
        flow += s;
    }
}

In this algorithm, we use the DFS algorithm to find an augmenting path. This algorithm adds at least one unit to the existing flow in each step, and since the time complexity of DFS is linear, the algorithm has a time complexity of \(O(ef)\), where e is the number of edges and f is the maximum flow value.

If we had used the BFS algorithm instead of DFS, the bound \(O(ve^2)\) would also hold, though we omit its proof here.

Finding Vertex and Edge Connectivity Numbers¶

Using the maximum flow algorithm, we can obtain vertex and edge connectivity numbers in polynomial time.

To find the edge connectivity number, for each edge we add two directed edges with weight 1 in opposite directions between the two vertices. Then we find the maximum flow between every pair of vertices, which equals the minimum cut. Since the minimum cut doesn't cut both directions of an edge, the minimum cut of this directed graph is equivalent to the undirected graph's. As every cut disconnects two vertices, this value is greater than the graph's edge connectivity number. However, since the minimum number of edges required to disconnect any two vertices corresponds to the minimum of these cuts, this minimum cut value equals the graph's edge connectivity number. The time complexity of this algorithm is \(O(v^3e)\) because the solution is smaller than the number of vertices.

To find the vertex connectivity number, we construct a new graph where each vertex is split into two nodes: an input node and an output node. For each original edge, we add two directed edges: from the input node of one vertex to the output node of the other, and vice versa. For each vertex, we connect its input node to its output node. Edges corresponding to original edges have infinite capacity, while intra-vertex edges have capacity 1. To determine how many vertices need to be removed to disconnect two target vertices, we find the minimum cut between those two vertices in this transformed graph. By calculating this value for all vertex pairs, we obtain the vertex connectivity number. The time complexity of this algorithm is \(O(v^3e)\) because the solution is smaller than the number of vertices.