disjointpath

Disjoint paths are a concept in graph theory referring to multiple paths that do not share certain elements of the graph. A set of paths is called vertex-disjoint if no two paths share any vertex; a set is edge-disjoint if no two paths share an edge. When considering paths between the same endpoints, it is common to distinguish between internally vertex-disjoint paths, where only the endpoints may be shared, and edge-disjoint paths, where edges are not shared but vertices may be.

A central result for two-terminal disjoint paths is Menger's theorem. For vertices s and t in a finite graph, the maximum number of pairwise internally vertex-disjoint s-t paths equals the minimum size of an s-t vertex cut (excluding s and t). A parallel statement holds for edge-disjoint s-t paths: the maximum number equals the minimum s-t edge cut. These dualities relate connectivity to the existence of multiple disjoint routes.

Computing disjoint paths is closely tied to network flow. To find the maximum number of edge-disjoint s-t paths, assign unit capacities to each edge and compute a maximum s-t flow; the value equals the maximum number of edge-disjoint paths, and the corresponding flow decomposes into such paths. For vertex-disjoint paths, perform vertex splitting: replace each vertex v by v_in and v_out connected by a single-capacity edge, then apply the same flow approach on the transformed network.

For multiple terminal pairs, the disjoint paths problem asks whether there exist pairwise disjoint paths connecting each specified pair. In general, this problem is NP-complete, but for fixed small k it is solvable in polynomial time, and there are specialized results for particular graph classes such as planar graphs.

Applications include network routing, reliability analysis, VLSI circuit design, and transportation planning, where finding multiple independent routes is a common objective.