This article was accepted into the corpus but its outbound wikilinks were never NER-processed — typical at the deepest BFS hop or when the run's entity cap was reached. No expansion funnel to show.
| Edge-disjoint paths problem | |
|---|---|
| Name | Edge-disjoint paths problem |
| Field | Graph theory, Combinatorics, Theoretical computer science |
| Introduced | 1960s |
| Notable | Disjoint paths problem, Menger's theorem, Robertson–Seymour theorem, Suurballe's algorithm |
Edge-disjoint paths problem The edge-disjoint paths problem asks whether, given a finite graph together with a collection of terminal pairs, there exist pairwise edge-disjoint paths connecting each prescribed pair. The problem arises in combinatorial optimization, routing, and telecommunication planning and links classical results such as Menger's theorem, algorithmic frameworks like Ford–Fulkerson algorithm, and structural theorems like the Robertson–Seymour theorem.
Given a finite undirected or directed graph G and k ordered terminal pairs (s1,t1), …, (sk,tk) drawn from the vertex set, the task is to find k paths P1, …, Pk such that Pi connects si to ti and no two paths share an edge. Instances are often parameterized by k, the size of the vertex set |V(G)|, or topological restrictions such as planarity; special formulations consider edge capacities, multigraphs, or demands specified by a multicommodity flow vector. Classical statements invoke connectivity measures and the edge version of Menger's theorem to characterize feasibility in uncapacitated settings.
The decision version is NP-complete in general, with hardness established by reductions from 3-SAT, Hamiltonian path, and other NP-complete problems. Variants include the directed versus undirected cases, the node-disjoint version, the edge-capacitated multicommodity flow variant, and the integer routing variant where integrality constraints mirror integer programming formulations. Parameterized complexity analyses consider k as a parameter, and results connect to fixed-parameter tractability and W[1]-hardness; for undirected graphs the related k-disjoint paths problem admits fixed-parameter algorithms via deep structural theory by Robertson–Seymour, while directed instances remain intractable under standard assumptions such as Exponential Time Hypothesis.
Polynomial-time algorithms exist for special families: Suurballe's algorithm yields pairwise edge-disjoint shortest paths in nonnegative weighted directed graphs for k=2 and relates to Dijkstra's algorithm and Bellman–Ford algorithm for single-source shortest paths. For undirected planar graphs, separator theorems by Lipton–Tarjan and structure theorems by Robertson–Seymour enable specialized algorithms. Combinatorial characterizations employ matchings and matroid intersection results such as those by Edmonds; packings of edge-disjoint paths relate to cut-covering theorems and max–min relations exemplified by Menger's theorem and generalized via Gomory–Hu tree constructions for global minimum cuts.
Edge-disjoint path instances can be formulated as integer multicommodity flow problems with binary variables indicating edge usage for each commodity; relaxations yield linear programs solvable by simplex algorithm or interior-point method and interpreted via duality in the spirit of Dantzig–Wolfe decomposition. Integrality gaps connect to polyhedral combinatorics studied using cutting-plane methods developed by Gomory and separation algorithms by Grötschel–Lovász–Schrijver. Reductions to single-commodity flows use edge-splitting and layering techniques inspired by Ford–Fulkerson algorithm and Hoffman–Kruskal theorem for totally unimodular matrices in special network classes.
Approximation strategies use randomized rounding of linear relaxations, region-growing techniques from work by Leighton–Rao, and metric embeddings via Arora-style methods to bound congestion. The problem admits polylogarithmic approximation ratios in some settings, while strength of inapproximability results derives from PCP theorems by Arora–Safra and hardness frameworks tied to Label Cover reductions; certain directed variants are hard to approximate within polynomial factors unless P = NP or collapses in the polynomial hierarchy occur. Bicriteria approximations trade congestion for route count, reflecting trade-offs formalized in results by Raghavan–Thompson and subsequent improvements by researchers affiliated with institutions such as MIT and Princeton University.
Special graph classes where tractability improves include planar graphs, trees, series–parallel graphs, and graphs excluding a fixed minor as per Robertson–Seymour structure theory; grid graphs and toroidal graphs feature in VLSI layout problems studied at Bell Labs. Applications span optical network provisioning in industrial deployments by companies such as Cisco Systems, frequency assignment in wireless networks studied at Bell Labs, evacuation routing modeled in operations research programs at CMU, and routing in backbone networks influenced by standards bodies like ITU. Practical heuristics derive from software tools developed in research groups at Bell Labs, IBM Research, and AT&T Labs.
Closely related problems include the vertex-disjoint paths problem, the edge-disjoint cycle packing problem, and k-commodity flow problems; generalizations consider capacity-specified edges, splittable versus unsplittable flows, and survivable network design problems related to work by Hale, Dinitz and others. Structural theorems and algorithmic frameworks connect to graph minor theory by Robertson–Seymour, matching theory by Edmonds, and routing lower bounds informed by probabilistic method techniques developed by Erdős.