Skip to content

Flows, Matchings & Path Covers

Max flow (Ford–Fulkerson idea)

Directed graph with capacity on edges, source s, sink t. Augment paths while residual capacity remains; DFS or BFS (Edmonds–Karp) finds augmenting paths.

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

bool bfsFlow(int s, int t, const vector<vector<int>>& cap, vector<vector<int>>& flow,
             vector<int>& parent) {
    int n = (int)cap.size();
    fill(parent.begin(), parent.end(), -1);
    vector<bool> vis(n, false);
    queue<int> q;
    vis[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < n; v++) {
            int residual = cap[u][v] - flow[u][v];
            if (!vis[v] && residual > 0) {
                vis[v] = true;
                parent[v] = u;
                if (v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int maxFlowEdmondsKarp(int s, int t, vector<vector<int>> cap) {
    int n = (int)cap.size();
    vector<vector<int>> flow(n, vector<int>(n, 0));
    vector<int> parent(n);
    int total = 0;
    while (bfsFlow(s, t, cap, flow, parent)) {
        int add = 1e9;
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            add = min(add, cap[u][v] - flow[u][v]);
        }
        for (int v = t; v != s; v = parent[v]) {
            int u = parent[v];
            flow[u][v] += add;
            flow[v][u] -= add;
        }
        total += add;
    }
    return total;
}

For large graphs use Dinic or push-relabel; for bipartite matching, Hopcroft–Karp is common.

Bipartite matching

Left–right bipartition; max matching equals max flow from super-source to super-sink with unit capacities, or specialized augmenting-path algorithms.

König’s theorem (bipartite)

In bipartite graphs, size of minimum vertex cover = size of maximum matching; complement gives maximum independent set on that side’s structure.

Path cover in DAG

Minimum path cover (vertex-disjoint paths covering all vertices) in a DAG: build bipartite graph \((u_{left}, v_{right})\) for each edge \(u \to v\); answer = \(|V|\) − max matching on that bipartite graph.