12.18 Vertex-Disjoint Paths

Edge-disjoint paths are allowed to share vertices.

algorithmsgraphsnetwork-flow

12.18 Vertex-Disjoint Paths

Problem

Edge-disjoint paths are allowed to share vertices. In some applications, that is not enough.

Consider two communication routes:

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

These paths do not share their first edges, but both depend on vertex C.

If C is a router, checkpoint, warehouse, switch, bridge, or processing station, then C is still a single point of failure.

The stronger requirement is:

Find the maximum number of paths from s to t that do not share internal vertices.

These are called vertex-disjoint paths.

Solution

Reduce the problem to maximum flow using node splitting.

For every internal vertex v, create:

v_in
v_out

and add:

v_in -> v_out
capacity = 1

Then transform every original edge:

u -> v

into:

u_out -> v_in

with capacity 1, or infinity if edge reuse is not the limiting factor.

The internal edge:

v_in -> v_out

forces at most one path to pass through v.

What Counts as Vertex-Disjoint?

Two paths are vertex-disjoint if they share no internal vertices.

They may share:

source
sink

unless the problem explicitly forbids that.

Example:

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

These are vertex-disjoint.

Example:

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

These are not vertex-disjoint because both use C.

Basic Transformation

Original graph:

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

Split internal vertices:

A_in -> A_out
B_in -> B_out
C_in -> C_out

each with capacity:

1

Original edge:

A -> C

becomes:

A_out -> C_in

Original edge:

C -> t

becomes:

C_out -> t

Now every path using C must cross:

C_in -> C_out

Since that edge has capacity 1, only one path can use C.

Source and Sink

Usually, s and t are not constrained.

You have two common choices.

First, do not split s and t.

Second, split them with infinite capacity:

s_in -> s_out
capacity = INF

t_in -> t_out
capacity = INF

In most implementations, the first option is simpler.

If the problem says every vertex, including source and sink, has capacity 1, then split them too. But most vertex-disjoint path problems allow all paths to start at the same source and end at the same sink.

Example

Graph:

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

Without vertex constraints, there are three edge-disjoint-looking routes:

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

But the first two both use C.

After node splitting, C has capacity 1.

Maximum vertex-disjoint paths:

2

One possible solution:

s -> A -> C -> t
s -> D -> t

The route through B -> C cannot be used at the same time because C is already occupied.

Flow Interpretation

Assign:

capacity = 1

to each internal vertex edge:

v_in -> v_out

Then compute max flow.

Each unit of flow represents one path.

Since every internal vertex edge has capacity 1, no internal vertex can carry two units of flow. Therefore no internal vertex appears in two selected paths.

Edge Capacities

There are two common variants.

Variant 1: Vertices Are the Only Constraint

Original edges may be used freely.

Use:

capacity = INF

on transformed original edges:

u_out -> v_in

and capacity 1 only on internal vertex edges.

Variant 2: Vertices and Edges Are Both Constrained

Each edge may be used at most once.

Use:

capacity = 1

on both:

v_in -> v_out

and:

u_out -> v_in

This computes paths that are both vertex-disjoint and edge-disjoint.

Most graph-theory vertex-disjoint path formulations only need vertex capacities.

Undirected Graphs

For an undirected edge:

u -- v

create two directed edges:

u_out -> v_in
v_out -> u_in

Again, use capacity 1 or infinity depending on whether the edge itself is constrained.

If undirected edges have shared capacity, do not blindly use two independent directed edges. That permits one unit in each direction simultaneously. Use an edge-capacity gadget if shared capacity matters.

Extracting the Paths

After max flow finishes:

  1. Follow positive-flow edges from s.
  2. Ignore internal edges when reporting the original path.
  3. Convert v_in and v_out back to v.
  4. Remove one unit of flow along the recovered route.
  5. Repeat until all flow is decomposed.

Example transformed path:

s -> A_in -> A_out -> C_in -> C_out -> t

Original path:

s -> A -> C -> t

Relationship to Menger's Theorem

Vertex-disjoint paths are governed by the vertex version of Menger's theorem:

The maximum number of internally vertex-disjoint paths from s to t equals the minimum number of internal vertices whose removal disconnects s from t.

Node splitting converts this vertex problem into an edge-capacity problem.

Then max-flow min-cut applies.

A minimum cut in the transformed graph identifies a minimum vertex separator in the original graph.

Finding a Minimum Vertex Cut

After max flow:

  1. Compute the minimum cut in the split graph.
  2. Inspect cut edges of the form:
v_in -> v_out
  1. The corresponding original vertices form a minimum vertex cut.

This is useful for reliability analysis.

If the minimum vertex cut has size 2, then removing two internal vertices is enough to disconnect the source and sink.

Example: Network Reliability

Suppose routers connect two data centers.

You want at least:

3

router-independent paths.

Build the split graph with capacity 1 on each router.

Then compute max flow.

If:

max flow >= 3

the network has enough independent routing.

If not, the minimum cut identifies the routers that create the bottleneck.

Implementation Pattern

Assign IDs:

in[v]  = 2 * v
out[v] = 2 * v + 1

For every internal vertex:

addEdge(in[v], out[v], 1)

For source and sink, either:

use original ID directly

or:

addEdge(in[s], out[s], INF)
addEdge(in[t], out[t], INF)

For every original directed edge:

u -> v

add:

addEdge(out[u], in[v], edgeCapacity)

where edgeCapacity is usually INF for pure vertex-disjoint paths.

Complexity

The transformation creates:

V' = 2V
E' = E + V

Then max flow runs on the transformed graph.

With Dinic, this is still practical for many sparse graphs.

For unit capacities, the problem often benefits from faster behavior in practice.

Common Mistakes

Splitting Source and Sink with Capacity 1

This restricts all paths to one total path. Usually source and sink should be unconstrained.

Using Capacity 1 on Original Edges Accidentally

That solves a stricter problem: edge-disjoint and vertex-disjoint paths.

Reporting Transformed Vertices Directly

Convert v_in and v_out back to v.

Forgetting Direction in Directed Graphs

The original edge u -> v becomes u_out -> v_in, not v_out -> u_in.

Mishandling Undirected Shared Edges

Two directed edges model bidirectional movement, not one shared undirected capacity.

Discussion

Vertex-disjoint paths are another example of turning an awkward constraint into a standard flow constraint. The original issue is that vertices, not edges, have capacity. Node splitting converts each vertex into an edge. After that, ordinary max-flow machinery applies.

This pattern is worth remembering beyond path problems. Any time a vertex has a throughput limit, splitting the vertex is usually the cleanest way to model it.

Takeaway

To compute vertex-disjoint paths, split each internal vertex into an input node and output node connected by a capacity-1 edge. Route original edges from output nodes to input nodes. Then compute maximum flow.

The resulting flow value equals the maximum number of internally vertex-disjoint paths, and a minimum cut in the transformed graph gives a minimum vertex separator.