disjointpaths

Disjointpaths is a concept in graph theory that concerns multiple paths in a graph that do not share resources. The most common distinctions are vertex-disjoint paths and edge-disjoint paths. Two paths are vertex-disjoint if they share no vertices, while two paths are edge-disjoint if they share no edges. When considering several terminal pairs, such as (s1, t1), (s2, t2), ..., (sk, tk), a disjoint paths problem asks whether there exist paths Pi from si to ti that are pairwise disjoint, typically meaning vertex-disjoint.

A key theoretical result related to vertex-disjoint paths is Menger's theorem. In undirected graphs, the theorem states that the maximum number of pairwise internally vertex-disjoint s–t paths equals the minimum size of an s–t vertex cut. This provides a bridge between path existence and cut structure, and it underpins many algorithmic approaches, especially via max-flow formulations.

Algorithmically, the disjoint paths problem can be reduced to network flow. To enforce vertex-disjointness, each vertex v is split into v_in and v_out with a unit capacity edge from v_in to v_out; original edges become edges from u_out to v_in with infinite capacity. A maximum s–t flow of value p corresponds to p vertex-disjoint s–t paths. For the special case of finding two disjoint s–t paths with minimum total length, Suurballe’s algorithm applies to weighted graphs and relies on shortest-path computations and a reweighting scheme; with vertex-disjointness desired, a vertex-splitting transformation is used.

Complexity-wise, in undirected graphs the disjoint paths problem is solvable in polynomial time for fixed k, while in directed graphs it is NP-complete when k is part of the input; fixed-k cases remain polynomially solvable. Disjoint paths have applications in network routing, circuit design, and reliability planning.