Degree-constrained network flows

A d -furcated flow is a network flow whose support graph has maximum out degree d . Take a single-sink multi-commodity flow problem on any network and with any set of routing demands. Then we show that the existence of feasible fractional flow with node congestion one implies the existence of a d -furcated flow with congestion at most 1+1/(d-1), for d ≥ 2. This result is tight, and sothe congestion gap for d -furcated flows is bounded andexactly equal to 1+ 1/(d-1). For the case d=1 (confluent flows), it is known that the congestion gap is unbounded, namely Θ(log n). Thus, allowing single-sink multicommodity network flows to increase their maximum out degree from one to two virtually eliminates this previously observed congestion gap.

Authors

• Patrick Donovan
• F. Bruce Shepherd
• Adrian Vetta
• Gordon T. Wilfong

Keywords

• congestion
• network flow