Edge-Disjoint Paths, in depth: Menger's theorem, unit-capacity max flow, the min-cut certificate and vertex-disjoint reductions

The problem, and Menger's theorem

The input is a graph G = (V, E), directed or undirected, possibly with parallel edges, and two distinct vertices s and t. A set of s–t paths is edge-disjoint if no edge appears in two of them. Two parallel cables are two edges, so they can carry two paths. The goal is the largest such set, written λ(s, t), together with the paths themselves.

Edge-disjoint is weaker than vertex-disjoint, where paths share no interior vertices. In the figure, the two answer paths share no vertex, but on many graphs the best edge-disjoint paths pass through a common router. If routers fail as well as links, edge-disjointness is the wrong model. The vertex-splitting reduction below handles that case.

Menger's theorem (1927): the maximum number of edge-disjoint s–t paths equals the minimum number of edges whose removal disconnects t from s. One direction is obvious. Every path must cross every s–t cut, and disjoint paths cross it on different edges, so paths ≤ cut size. The other direction, that some cut always matches, is what max-flow min-cut provides.

Why unit-capacity max flow solves it

Give every edge capacity 1 and compute a maximum flow from s to t. Because all capacities are integers, Ford–Fulkerson-style algorithms produce an integral maximum flow, so every edge carries 0 or 1 unit. A 0/1 flow of value k breaks into k paths that each use their own edges. In the other direction, k disjoint paths give a flow of value k. So the max flow equals λ(s, t), and by max-flow min-cut it equals the minimum cut, which proves Menger's theorem.

For an undirected edge {u, v}, the flow may go either way but uses one unit of capacity in total. Keep one signed flow value per edge, f ∈ {−1, 0, +1} relative to a stored orientation (u, v). The residual capacity from u is 1 − f and from v is 1 + f. After one unit goes u→v, the residual capacity from v is 2: one unit to cancel the existing flow and one to send flow back. This is the standard undirected treatment, and it makes opposite flows on one edge cancel automatically.

The trap, and how residual paths escape it

The graph in the figure has edges s–a, a–b, b–t, s–c, c–b, a–d and d–t. Three s–t paths have length 3: s-a-b-t, s-c-b-t and s-a-d-t. A greedy method that takes a shortest path and deletes its edges might take s-a-b-t first. That uses both s–a and b–t, so c can reach b but nothing leads from b to t, and greedy stops at one path. The answer is two.

Round 2 shows how flow algorithms handle a bad early choice: they do not backtrack, they reroute. Traversing a–b backwards hands a's onward route to b's incoming traffic. The final BFS reaches only {s}, and the edges leaving that set, s–a and s–c, form a cut of size 2. Two paths and a two-edge cut, so neither can be improved.

A tested implementation

The implementation stores one signed flow per undirected edge, as described above, and augments along BFS paths until t is unreachable. It returns three things you need in practice: the count, the paths, and the cut edges that prove the count is optimal.

from collections import deque

def edge_disjoint_paths(n, edges, s, t):
    """Undirected multigraph; edges = list of (u, v). Returns (paths, cut_edge_ids).
    flow[i] in {-1, 0, +1}: +1 means one unit travels u->v on edge i."""
    if s == t:
        raise ValueError("s and t must differ")
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        if u != v:                                 # a self-loop never helps
            adj[u].append(i); adj[v].append(i)
    flow = [0] * len(edges)

    def residual(i, frm):                          # spare capacity leaving frm on edge i
        return 1 - flow[i] if frm == edges[i][0] else 1 + flow[i]

    def bfs():
        prev = [None] * n; prev[s] = -1
        q = deque([s])
        while q:
            x = q.popleft()
            for i in adj[x]:
                u, v = edges[i]; y = v if x == u else u
                if prev[y] is None and residual(i, x) > 0:
                    prev[y] = (i, x); q.append(y)
                    if y == t:
                        return prev
        return prev

    while True:
        prev = bfs()
        if prev[t] is None:
            break
        y = t
        while y != s:                              # push one unit along the path
            i, x = prev[y]
            flow[i] += 1 if x == edges[i][0] else -1
            y = x

    reach = {v for v in range(n) if prev[v] is not None}
    cut = [i for i, (u, v) in enumerate(edges) if (u in reach) != (v in reach)]

    out = [[] for _ in range(n)]                   # decompose: follow +flow arcs from s
    for i, (u, v) in enumerate(edges):
        if flow[i] == 1: out[u].append(v)
        elif flow[i] == -1: out[v].append(u)
    paths = []
    while out[s]:
        path, x = [s], s
        while x != t:
            x = out[x].pop()
            if x in path:                          # flow cycle: splice it out
                path = path[:path.index(x)]
            path.append(x)
        paths.append(path)
    return paths, cut

On the trap graph it returns [s, c, b, t] and [s, a, d, t] with cut {s–a, s–c}. A max flow can contain cycles, and following flow arcs from s can then produce a walk that revisits a vertex. The splice step cuts the loop out, and the walk stays edge-disjoint from the other paths. On 1,500 random multigraphs with up to 8 vertices, parallel edges and self-loops, the number of paths, the size of the returned cut and a brute-force minimum cut over all vertex subsets agreed every time, and every returned path was simple and used each edge no more often than it appears.

Complexity, and global connectivity

Each augmentation adds one unit of flow and costs O(V + E) for the BFS. The flow is at most k = min(deg(s), deg(t)), so the simple algorithm runs in O(k·E). For the small k typical of resilience questions (2, 3 or 4 paths), that is a few linear passes and hard to beat.

When k is large, Dinic's algorithm on unit-capacity graphs runs in O(E·min(√E, V^2/3)) (Even and Tarjan, 1975). The better-known O(E√V) bound needs a unit network, where every vertex other than s and t has in-degree 1 or out-degree 1. That is what vertex splitting and bipartite matching produce. Edge-disjoint paths in a general graph do not get it.

For the global edge connectivity λ(G), meaning the fewest edges whose removal disconnects anything: fix any s, compute λ(s, t) for every other t, and take the minimum. That costs V−1 flows, and it is correct because any minimum cut separates s from some t. Stoer–Wagner does it without flows in O(VE + V² log V). For λ(s, t) between all pairs, a Gomory–Hu tree stores every pairwise answer using only V−1 flow computations.

Variants

• Vertex-disjoint paths. Split each interior vertex into an in-copy and an out-copy joined by a capacity-1 arc. Every path through v must use that arc, so at most one path passes through v. Any directed max-flow routine on the arcs below gives the answer. Menger's vertex version says it equals the smallest vertex separator. If s and t are adjacent, the direct edge is one path that no separator can block.

  def vertex_split(n, edges, s, t):
      """Directed arcs (tail, head, cap) whose max flow = max vertex-disjoint s-t paths.
      Vertex v becomes v_in = 2v and v_out = 2v + 1, joined by one unit of capacity."""
      arcs = [(2 * v, 2 * v + 1, 1) for v in range(n) if v not in (s, t)]
      for u, v in edges:                    # undirected edge -> two arcs, out -> in
          arcs.append((2 * u + 1, 2 * v, 1))
          arcs.append((2 * v + 1, 2 * u, 1))
      return arcs, 2 * s + 1, 2 * t         # source = s_out, sink = t_in

• Directed graphs. Use each arc in its own direction only, with capacity 1 and no reverse capacity. The flow argument is unchanged.
• Minimum total length. Among all sets of k disjoint paths, find the cheapest. That is min-cost flow with value k. For k = 2, Suurballe's algorithm does it with two Dijkstra runs.
• Several source–sink pairs. Routing pairs (s1, t1), ..., (sk, tk) on edge-disjoint paths is NP-hard in general. In directed graphs even two pairs is NP-hard (Fortune, Hopcroft and Wyllie, 1980). Flow techniques do not apply because the commodities cannot share one flow. Practical systems use integer programming or heuristics.
• Shared-risk groups. Two fibres in the same duct or conduit are logically disjoint but physically fate-shared. Requiring paths that avoid shared risk link groups (SRLGs) is NP-hard in general. A useful approximation is to merge each group into a single edge before running the algorithm, though that can be conservative.

Using it for network resilience

In network and infrastructure work the algorithm is mostly used as an audit:

1. Export the topology with one edge per physical link, keeping parallel links. If the risk model includes devices, run the vertex-split version.
2. For each critical pair (two regions, a service and its database, a site and its upstream), compute λ(s, t) and the cut. Store the cut edges, because those are the links that need protection.
3. Compare λ with the target: k disjoint paths survive k−1 simultaneous link failures. Flag pairs below target, and attach the cut so engineers know which links to add capacity beside.
4. Re-run on every topology change in CI, and fail the change if any critical pair drops below target. Diff the cut sets, since a new single point of failure shows up as a cut of size 1.
5. Use the paths as candidates for pinned or traffic-engineered routes. Use Suurballe or min-cost flow when latency matters more than the count.

The trade-offs are simple. Edge-disjoint counts are cheap and give certificates, but they overstate resilience when vertices or shared conduits fail. Vertex-disjoint and SRLG-aware models are more honest but stricter, and SRLG constraints quickly become intractable. Report all three numbers if you can compute them.

Failure modes

• Two independent arcs per undirected edge, each of capacity 1. The count comes out right, but the decomposition can show flow both ways on one cable, which is the same edge used twice. Use one signed flow per edge as above, or cancel opposite flows before decomposing.
• Collapsing parallel edges. Deduplicating an edge list turns two cables into one and undercounts λ. Keep multiplicities, or set capacity equal to the multiplicity.
• Greedy delete-and-repeat. As the trap shows, it can return fewer paths than the maximum. Always use residual cancellation.
• Assuming the walks are simple. Without the splice step, decomposition can return walks with loops, and later code that maps them to routes fails.
• Calling it vertex-disjoint. Edge-disjoint paths may share a router. State which model was used in every report.
• s = t, or s not connected to t. Define the behaviour: raise an error for s = t, return zero paths and an empty cut otherwise, and test both cases.

What to do next

1. Run the implementation on the trap graph and confirm two paths and the cut {s–a, s–c}. Then add edges s–e and e–a. The count stays 2, but the cut moves away from s to {a–d, b–t}.
2. Port the brute-force cross-check into your test suite: on small random multigraphs, the number of paths must equal the size of the returned cut and the minimum cut over all subsets.
3. Re-read the max-flow min-cut theorem and Ford–Fulkerson to see why integrality holds.
4. Wrap the vertex-split construction around a directed max-flow routine and compare edge- and vertex-disjoint counts on your own topology.
5. Compute global edge connectivity with V−1 flows and with Stoer–Wagner, and check that they agree.
6. Turn the operational audit into a CI check that fails a topology change when any critical pair drops below its target λ.
7. When the cost of the paths matters, move on to Suurballe's algorithm.