12.17 Edge-Disjoint Paths

Problem

Suppose you are designing a communication network between two data centers.

A single path between the source and destination may be sufficient under normal conditions. But if one cable fails, communication stops.

A more reliable design uses multiple independent routes.

Example:

s -> A -> t
s -> B -> t
s -> C -> t

Even if one route fails, traffic can continue using the others.

This leads to an important graph problem:

How many completely independent paths exist between two vertices?

More formally, we seek the maximum number of edge-disjoint paths.

Solution

Reduce the problem to maximum flow.

Assign capacity:

to every edge.

Then compute the maximum flow from source to sink.

The resulting maximum-flow value equals the maximum number of edge-disjoint paths.

This is one of the most elegant applications of network flow.

What Are Edge-Disjoint Paths?

Two paths are edge-disjoint if they share no edges.

Example:

Path 1:
s -> A -> t

Path 2:
s -> B -> t

These paths are edge-disjoint.

Example:

Path 1:
s -> A -> B -> t

Path 2:
s -> C -> B -> t

These paths share:

B -> t

and therefore are not edge-disjoint.

The goal is to maximize the number of pairwise edge-disjoint source-to-sink paths.

Example

Consider:

        A
      /   \\ns               t
      \   /
        B

Edges:

s -> A
A -> t

s -> B
B -> t

Two edge-disjoint paths exist:

s -> A -> t
s -> B -> t

Answer:

Flow Interpretation

Assign capacity:

to every edge.

Edge	Capacity
s -> A	1
A -> t	1
s -> B	1
B -> t	1

Maximum flow:

Each unit of flow corresponds to one path.

Because capacities are one, no edge can be reused.

Thus:

maximum flow
=
maximum number of edge-disjoint paths

Why Unit Capacities Matter

Suppose edge:

A -> B

had capacity:

A maximum-flow algorithm might send:

units through that edge.

This would allow multiple paths to share the same edge.

For edge-disjoint paths, every edge must be usable at most once.

Setting:

capacity = 1

enforces this requirement automatically.

Path Decomposition

After computing the flow, we can recover the actual paths.

Consider:

s -> A -> t
s -> B -> t

Flow:

Edge	Flow
s -> A	1
A -> t	1
s -> B	1
B -> t	1

Start from the source and follow positive-flow edges.

First path:

s -> A -> t

Remove it.

Second path:

s -> B -> t

Continue until all flow is exhausted.

This process is called flow decomposition.

A More Interesting Example

Network:

s -> A
s -> B

A -> C
B -> C

C -> t

All capacities:

Although there appear to be two routes:

s -> A -> C -> t
s -> B -> C -> t

they both require:

C -> t

The edge:

C -> t

is the bottleneck.

Maximum flow:

Therefore:

maximum edge-disjoint paths = 1

Relationship to Cuts

Consider the previous graph.

The cut:

A = {s, A, B, C}
B = {t}

contains one crossing edge:

C -> t

Capacity:

By the max-flow min-cut theorem:

max flow = min cut = 1

Therefore only one edge-disjoint path can exist.

This illustrates a deeper theorem.

Menger's Theorem

One of the central results in graph theory states:

The maximum number of edge-disjoint paths between two vertices equals the minimum number of edges whose removal disconnects them.

This is Menger's theorem.

Flow algorithms provide an efficient proof and computation method.

Instead of searching directly for disjoint paths, we compute a maximum flow.

Directed Graph Example

Consider:

s -> A -> t
s -> B -> t
A -> B

Capacities:

Maximum flow:

Two edge-disjoint paths exist:

s -> A -> t
s -> B -> t

The extra edge:

A -> B

does not increase the answer because it does not create an additional independent route.

Undirected Graphs

For undirected graphs:

u -- v

replace each edge with:

u -> v
v -> u

both having capacity:

Then apply the same maximum-flow reduction.

Be careful when modeling shared undirected capacity. In many formulations, additional care is required to prevent simultaneous use in both directions.

Network Reliability

A communication network:

Data Center A
      ↓
Internet Backbone
      ↓
Data Center B

may require:

independent routes.

To verify the design:

Build the graph.
Assign capacity 1 to each link.
Compute maximum flow.

If:

max flow ≥ k

the network supports k edge-disjoint paths.

Transportation Example

Suppose emergency supplies must travel from a warehouse to a city.

Each road can be used by only one convoy.

Road network:

Warehouse
   ↓
Roads
   ↓
City

The maximum number of simultaneous convoys equals the number of edge-disjoint paths.

Again, maximum flow solves the problem directly.

Extracting the Paths

After computing max flow:

flow = k

repeat:

Find a path using edges carrying flow.
Record the path.
Remove one unit of flow along the path.

After k iterations:

all paths recovered

This works because every integral flow can be decomposed into paths and cycles.

With unit capacities, the decomposition is especially simple.

Complexity

Let:

V = vertices
E = edges

Using Dinic:

O(V²E)

in general.

Because capacities are unit:

O(E√V)

often applies.

This makes edge-disjoint path problems quite practical even for large graphs.

Common Mistakes

Forgetting Unit Capacities

Capacities greater than one allow multiple paths to share an edge.

Counting Paths Manually

The graph may contain many overlapping routes. Maximum flow automatically handles all interactions.

Ignoring Direction

Directed and undirected graphs produce different answers.

Forgetting Path Extraction

The flow value gives the number of paths, but many applications also require the actual routes.

Edge-Disjoint vs Vertex-Disjoint

Edge-disjoint paths may share vertices.

Example:

s -> A -> C -> t
s -> B -> C -> t

share vertex:

but not necessarily edges.

If vertices must also be unique, a different model is needed.

The next recipe introduces vertex-disjoint paths and shows how vertex capacities and node splitting provide the solution.

Discussion

Edge-disjoint paths provide a beautiful example of modeling. The original problem does not mention capacities, residual graphs, or augmenting paths. Yet a simple capacity assignment transforms it into a maximum-flow instance.

This reduction is more than a clever trick. It reveals that network reliability, connectivity, and routing are fundamentally flow problems.

Takeaway

To compute the maximum number of edge-disjoint paths between two vertices, assign capacity 1 to every edge and compute the maximum flow. The resulting flow value equals the maximum number of independent routes.

This reduction is a direct consequence of the max-flow min-cut theorem and provides an efficient way to solve reliability, routing, and connectivity problems. The next recipe extends the idea to vertex-disjoint paths, where vertices rather than edges become the constrained resource.