Hardness of routing with congestion in directed graphs

ABSTRACT

Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an N^Ω(1/c(N)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have N^{O(log logN)}-time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor N^O(1/c(N)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of N^Ω(1/c) for c ranging from 1 to Θ((log n)/(log log n)).

A solution to the routing problem involves selecting which pairs tobe routed and what paths to assign to each routed pair. Two naturalrestrictions can be placed on input instances to eliminate one ofthese aspects of the problem complexity. The first restriction is toconsider instances with perfect completeness; an optimalsolution is able to route all pairs with congestion 1 in suchinstances. The second restriction to consider is the uniquepaths property where each source-destination pair has a unique pathconnecting it in the instance. An important aspect of our result isthat it holds on instances with any one of these tworestrictions. Our hardness construction with the perfectcompleteness restriction allows us to conclude that the directedcongestion minimization problem, where the goal is to route allpairs with minimum congestion, is hard to approximate to within afactor of Ω(log N/log log N). On the other hand, thehardness construction with unique paths property allows us toconclude an N^Ω(1/c) inapproximability bound also for theall-or-nothing flow problem. This is in a sharp contrast to theundirected setting where the all-or-nothing flow problem is known tobe approximable to within a poly-logarithmic factor.

REFERENCES

• 1: Matthew Andrews , Julia Chuzhoy , Lisa Zhang, Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.226-244, October 23-25, 2005 [doi>10.1109/SFCS.2005.41]
• 2: Matthew Andrews , Lisa Zhang, Hardness of the undirected congestion minimization problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060633]
• 3: 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]
• 4: Matthew Andrews , Lisa Zhang, Logarithmic hardness of the directed congestion minimization problem, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132592]
• 5: 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
• 6: 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]
• 7: Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Multicommodity flow, well-linked terminals, and routing problems, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060618]
• 8: J. Chuzhoy and S. Khanna. Hardness of directed routing with congestion. ECCC Technical Report TR06-109, August 2006. http://eccc.hpi-web.de/eccc-reports/2006/TR06-109/index.html.
• 9: 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]
• 10: Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M ]
• 11: J. Friedman. A note on the second eigenvalue of regular graphs. Manuscript (personal communication), 2006.
• 12: 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]
• 13: V. Guruswami and K. Talwar. Hardness of low-congestion routing in undirected graphs. Manuscript, May 2005.
• 14: V. Guruswami and K. Talwar. Hardness of low congestion routing in directed graphs. ECCC Technical Report TR06-141, 2006, http://eccc.hpi-web.de/eccc-reports/2006/TR06-141/index.html.
• 15: J. Håstad. Clique is hard to approximate within n^1-ε. Acta Mathematica, 182:105--142, 1999.
• 16: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 17: J. Håstad and S. Khot. Query efficient PCPs with perfect completeness. Theory of Computing, 1(7):119--148, 2005.
• 18: S. Khot, Improved Inapproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.600, October 14-17, 2001
• 19: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, Massachusetts Institute of Technology, 1996
• 20: Stavros G. Kolliopoulos , Clifford Stein, Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.153-168, June 22-24, 1998
• 21: 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]
• 22: 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
• 23: 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

General Terms:
Algorithms, Theory

Keywords:
all-or-nothing flow, congestion minimization, edge-disjoint paths, hardness of approximation, integrality gap, multicommodity flow