Hardness of the undirected edge-disjoint paths problem

ABSTRACT

We show that there is no log ^{1 over 3-ε} 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: 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
• 3: 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]
• 4: 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
• 5: 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]
• 6: Yefim Dinitz , Naveen Garg , Michel Goemans, On the Single-Source Unsplittable Flow Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.290, November 08-11, 1998
• 7: P. Erdös and H. Sachs. Reguläre graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. Halle-Wittenburg (Math. Nat.), 12:251--257, 1963.
• 8: 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]
• 9: N. Garg, V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18:3--20, 1997.
• 10: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.19-28, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301262]
• 11: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 12: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 13: 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]
• 14: Jon Kleinberg , Éva Tardos, Approximations for the disjoint paths problem in high-diameter planar networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.26-35, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225075]
• 15: 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
• 16: 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
• 17: 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
• 18: T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 422--431, 1988.
• 19: 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]
• 20: 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]
• 21: 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
• 22: 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]
• 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

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

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