pathpacking

Pathpacking is a problem in graph theory focused on selecting a collection of paths that do not interfere with each other, according to a chosen notion of disjointness (most often vertex-disjoint or edge-disjoint). A common formulation fixes a set of terminal pairs (s1, t1), (s2, t2), ..., (sk, tk) and asks whether there exist pairwise disjoint paths connecting each pair. More generally, one seeks the maximum number of disjoint s_i–t_i paths that can be realized from a given collection of terminal pairs.

In the vertex-disjoint version, paths may share neither vertices nor, in the edge-disjoint version, edges. A standard technique to handle vertex-disjoint paths is to transform the graph by splitting each vertex into an in- and out-vertex connected by a unit-capacity edge, turning vertex-disjoint paths into edge-disjoint ones in the transformed graph. For edge-disjoint paths, classic network-flow methods apply: max-flow with unit capacities yields the maximum number of edge-disjoint s–t paths.

Algorithmic status varies. In undirected graphs, the problem of packing k disjoint s_i–t_i paths is solvable in polynomial time for fixed k (the k-disjoint paths problem), due to deep structural results. When the number of terminal pairs is part of the input, the problem becomes significantly harder and is generally NP-hard. The directed version is typically more challenging and is known to be NP-complete for several natural formulations, though fixed-parameter and specialized algorithms exist in certain settings.

Applications of pathpacking appear in network routing for fault tolerance, VLSI circuit design, and parallel computing, where non-overlapping routes minimize interference. The problem connects to fundamental theorems such as Menger’s theorem and to core tools in combinatorial optimization like max-flow min-cut and graph minor theory.

---