Multicommodity flow, well-linked terminals, and routing problems

ABSTRACT

We study multicommodity routing problems in both edge and node capacitated undirected graphs. The input to each problem is a capacitated graph G=(V,E) and a set Τ of node pairs. In the simplest setting, the goal is to route a unit of flow for as many pairs as possible subject to the edge (node) capacity constraints. If the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. If we allow fractional routings of the flow, it is known as the all-or-nothing flow problem. The nodes in Τ are referred to as terminals.In recent work [8,9], the authors obtained the first poly-logarithmic approximation algorithms for some edge routing problems. A key idea in these algorithms is to decompose an instance into a collection of instances in which the terminals are well-linked. Informally speaking, a set of nodes is well-linked in a graph if it does not have small separators. A decomposition into well-linked instances was previously achieved in [8] via räcke's hierarchical graph decomposition for oblivious routing [32]. In this paper, we design a simple new decomposition algorithm that is based on computing sparse cuts in a graph. Our new algorithm improves the earlier results for edge routing problems. Another important advantage of the algorithm is that it also applies to node-capacitated problems. We note that for oblivious routing with node capacities, an Ω√n) lower bound is known on the congestion [18], and hence the oblivious routing approach cannot yield poly-logarithmic bounds for well-linked decompositions. Using the new decomposition, we obtain a poly-logarithmic approximation for the node capacitated all-or-nothing flow problem in general graphs and node-disjoint path problem in planar graphs with O(1) congestion. We also show that the flow-cut gap for product multicommodity flows in node capacitated planar graphs is O(1), improving upon the O(log n) bound from [28].

REFERENCES

• 1: Amit Agarwal , Moses Charikar , Konstantin Makarychev , Yury Makarychev, O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060675]
• 2: Noga Alon , Paul Seymour , Robin Thomas, Planar Separators, SIAM Journal on Discrete Mathematics, v.7 n.2, p.184-193, May 1994 [doi>10.1137/S0895480191198768]
• 3: Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780557]
• 4: Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060632]
• 5: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 6: Yonatan Aumann , Yuval Rabani, Improved bounds for all optical routing, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.567-576, January 22-24, 1995, San Francisco, California, United States
• 7: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 8: Alok Baveja , Aravind Srinivasan, Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems, Mathematics of Operations Research, v.25 n.2, p.255-280, May 2000 [doi>10.1287/moor.25.2.255.12228]
• 9: Chandra Chekuri , Sanjeev Khanna, On Multidimensional Packing Problems, SIAM Journal on Computing, v.33 n.4, p.837-851, 2004 [doi>10.1137/S0097539799356265]
• 10: Chandra Chekuri , Sanjeev Khanna, Edge disjoint paths revisited, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, The all-or-nothing multicommodity flow problem, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007383]
• 12: C. Chekuri , S. Khanna , F. B. Shepherd, Edge-Disjoint Paths in Planar Graphs, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.71-80, October 17-19, 2004 [doi>10.1109/FOCS.2004.27]
• 13: C. Chekuri, M. Mydlarz, and F. B. Shepherd. Multicommodity Demand Flow in a Tree and Packing Integer Programs. Submitted. Preliminary version in Proc. of ICALP, 2003.
• 14: J. Chuzhoy and S. Khanna. Improved Hardness Results and Integrality Gaps forEdge Disjoint Paths. Manuscript, 2005.
• 15: Julia Chuzhoy , Joseph (Seffi) Naor, New hardness results for congestion minimization and machine scheduling, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007364]
• 16: Erik D. Demaine , MohammadTaghi Hajiaghayi, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 17: S. Even, A. Itai and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. on Computing, Vol 5, 691--703, 1976.
• 18: Uriel Feige , MohammadTaghi Hajiaghayi , James R. Lee, Improved approximation algorithms for minimum-weight vertex separators, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060674]
• 19: J. Fakcheroenphol and K. Talwar. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. Proc. of APPROX, 2003.
• 20: A. Frank. Edge-disjoint paths in planar graphs. J. of Combinatorial Theory, Ser. B., No. 2 (1985), 164--178.
• 21: A. Frank. Packing paths, cuts, and circuits - a survey. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, eds., Paths, Flows and VLSI-Layout, 49--100. Springer Verlag, Berlin, 1990.
• 22: S. Fortune, J. Hopcroft and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111--121, 1980.
• 23: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 24: N. Garg, V. Vazirani, M. Yannakakis. Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees. Algorithmica, 18(1):3--20, 1997.
• 25: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Journal of Computer and System Sciences, v.67 n.3, p.473-496, November 2003 [doi>10.1016/S0022-0000(03)00066-7]
• 26: Mohammad T. Hajiaghayi , Robert D. Kleinberg , Tom Leighton , Harald Räcke, Oblivious routing on node-capacitated and directed graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 27: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 28: R. M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, Eds., New York: Plenum Press, 1972, 85--103.
• 29: P. Klein, S. Plotkin and S. Rao. Planar graphs, multicommodity flow, and network decomposition. Proc. of STOC, 1993.
• 30: Jon Kleinberg , Éva Tardos, Approximations for the disjoint paths problem in high-diameter planar networks, Journal of Computer and System Sciences, v.57 n.1, p.61-73, Aug. 1998 [doi>10.1006/jcss.1998.1579]
• 31: J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
• 32: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 33: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 34: Jon M. Kleinberg, Decision algorithms for unsplittable flow and the half-disjoint paths problem, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.530-539, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276867]
• 35: S. G. Kolliopoulos and C. Stein. Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs. Math. Programming, series A, (99):63--87, 2004.
• 36: Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.184-193, January 06-08, 2002, San Francisco, California
• 37: Petr Kolman, A note on the greedy algorithm for the unsplittable flow problem, Information Processing Letters, v.88 n.3, p.101-105, 15 November 2003 [doi>10.1016/S0020-0190(03)00351-X]
• 38: M. R. Kramer and J. L. van Leeuwen. The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits. VLSI-Theory (F. P. Preparata ed.) {Advances in Computing Research, Volume 2}, JAI Press, Greenwich, Connecticut, 1984, 129--146.
• 39: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 40: Tom Leighton , Satish Rao , Aravind Srinivasan, Multicommodity Flow and Circuit Switching, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.459, January 06-09, 1998 [doi>10.1109/HICSS.1998.649241]
• 41: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 42: James F. Lynch, The equivalence of theorem proving and the interconnection problem, ACM SIGDA Newsletter, v.5 n.3, p.31-36, September 1975 [doi>10.1145/1061425.1061430]
• 43: H. Okamura and P.D. Seymour. Multicommodity flows in planar graphs. of Combinatorial Theory, Series B, 31 (1981) 75--81.
• 44: James K. Park , Cynthia A. Phillips, Finding minimum-quotient cuts in planar graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.766-775, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167284]
• 45: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 46: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 47: S. Rao Finding near optimal separators in planar graphs. Proc. of FOCS, 1987.
• 48: N. Robertson and P. D. Seymour. Outline of a disjoint paths algorithm. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, Eds., Paths, Flows and VLSI-Layout. Springer-Verlag, Berlin, 1990.
• 49: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
• 50: Neil Robertson , P. D. Seymour, Graph minors: X. obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, v.52 n.2, p.153-190, July 1991 [doi>10.1016/0095-8956(91)90061-N]
• 51: P. D. Seymour and R. Thomas. Call Routing and the Ratcatcher. Combinatorica, 14(2): 217-241 (1994).
• 52: A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin Hiedelberg, 2003.
• 53: A. Srinivasan, Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.416, October 19-22, 1997
• 54: Kasturi Varadarajan , Ganesh Venkataraman, Graph decomposition and a greedy algorithm for edge-disjoint paths, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
all-or-nothing flow, disjoint paths, flow-cut gaps, multicommodity flow, network routing