Logarithmic hardness of the undirected edge-disjoint paths problem

ABSTRACT

We show that there is no log^{⅓ − ϵ} M approximation for the undirected Edge-Disjoint Paths problem unless NP ⊆ ZPTIME(n^polylog(n)), where M is the size of the graph and ϵ is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.

REFERENCES

• 1: Matthew Andrews, Hardness of Buy-at-Bulk Network Design, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.115-124, October 17-19, 2004 [doi>10.1109/FOCS.2004.32]
• 2: 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]
• 3: 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]
• 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: 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]
• 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: Yossi Azar , Oded Regev, Strongly Polynomial Algorithms for the Unsplittable Flow Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.15-29, June 13-15, 2001
• 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, Edge disjoint paths revisited, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: 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]
• 11: Chandra Chekuri , Sanjeev Khanna , F. Bruce Shepherd, Edge-disjoint paths in Planar graphs with constant congestion, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132621]
• 12: Chekuri, C., Khanna, S., and Shepherd, B. 2006b. An O(&nradic;) approximation and integrality gap for disjoint paths and UFP. Theory Comput. 2, 137--146.
• 13: Dinitz, Y., Garg, N., and Goemans, M. 1999. On the single source unsplittable flow problem. Combinatorica 19, 1, 17--41,
• 14: Erdös, P., and Sachs, H. 1963. Reguläre graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.) 12, 251--257.
• 15: Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra , Mario Szegedy, Interactive proofs and the hardness of approximating cliques, Journal of the ACM (JACM), v.43 n.2, p.268-292, March 1996 [doi>10.1145/226643.226652]
• 16: Fortune, S., Hopcroft, J., and Wyllie, J. 1980. The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10, 2, 111--121.
• 17: Garg, N., Vazirani, V., and Yannakakis, M. 1997. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3--20,
• 18: 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]
• 19: Karp, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds, pp. 85--103.
• 20: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 21: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 22: 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]
• 23: 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
• 24: 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 ]
• 25: 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
• 26: 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
• 27: 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]
• 28: Bin Ma , Lusheng Wang, On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints, Journal of Computer and System Sciences, v.60 n.1, p.1-12, Feb. 2000 [doi>10.1006/jcss.1999.1661 ]
• 29: 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]
• 30: Robertson, N., and Seymour, P. D. 1990. Outline of a disjoint paths algorithm. In Paths, Flows and VLSI-Layout, B. Korte, L. Lovász, H. J. Prömel and A. Schrijver, Eds. Springer-Verlag, New York.
• 31: Alex Samorodnitsky , Luca Trevisan, A PCP characterization of NP with optimal amortized query complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.191-199, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335329]
• 32: 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
• 33: Luca Trevisan, Non-approximability results for optimization problems on bounded degree instances, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.453-461, July 2001, Hersonissos, Greece [doi>10.1145/380752.380839]
• 34: 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

Keywords:
Hardness of approximation, edge-disjoint paths, undirected graphs