Degree-constrained network flows

ABSTRACT

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.

As a corollary we obtain a factor 1 + 1/(d-1)-approximation algorithm for the problem of finding a minimum congestion d-furcated flow; we also prove that this problem is max SNP-hard. Using known techniques these results also extend to degree-constrained unsplittable routing,where each individual demand must be routed along a unique path.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: Jiangzhuo Chen , Robert D. Kleinberg , László Lovász , Rajmohan Rajaraman , Ravi Sundaram , Adrian Vetta, (Almost) tight bounds and existence theorems for confluent flows, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007432]
• 3: Jiangzhuo Chen , Rajmohan Rajaraman , Ravi Sundaram, Meet and merge: approximation algorithms for confluent flows, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780598]
• 4: Y. Dinitz, N. Garg and M. Goemans, "On the single-source unsplittable flow problem" , Combinatorica, 19, pp. 17--41, 1999.
• 5: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 6: Stavros G. Kolliopoulos , Clifford Stein, Improved Approximation Algorithms for Unsplittable Flow Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.426, October 19-22, 1997
• 7: J. Fong, A. C. Gilbert, S. Kannan, and M. Strauss, "Better alternatives to OSPF routing" , Algorithmica (Special issue on network design), 43(1-2), pp. 113--131, 2005
• 8: B. Fortz and M. Thorup, "Optimizing OSPF/IS-IS weights in a changing world" , IEEE Journal on Selected Areas in Communications (Special Issue on Recent Advances on Fundamentals of Network Management), 20(4), pp. 756--767, 2002.
• 9: B. Shepherd and A. Vetta, "Visualizing, finding and packing dijoins", in D. Avis, A. Hertz, O. Marcotte (eds.), Graph Theory and Combinatorial Optimization, Kluwer, pp. 219--254, 2005.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms

Keywords:
congestion, network flow