Multicommodity Flow, Well-Linked Terminals, and Routing Problems

We study multicommodity routing problems in both edge and node capacitated undirected graphs. In the simplest setting, the input to each problem is a capacitated graph G = (V,E) and a set T of k node pairs. The goal is to route a unit of flow for as many pairs as possible subject to the capacity of the graph. If the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. Otherwise, if we allow fractional routings of the flow, it is known as the all-or-nothing flow problem. The nodes in T are referred to as the terminals.