research-article

Free access

Breaking o(n^1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two

Authors:

Ken-ichi Kawarabayashi,

Yusuke KobayashiAuthors Info & Claims

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

Pages 81 - 88

https://doi.org/10.1145/1993636.1993648

Published: 06 June 2011 Publication History

Abstract

In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is a polynomial time algorithm that finds at least OPT / r edge-disjoint paths, where OPT is the maximum possible. Currently, an O(n^1/2)-approximation algorithm is best known for this problem even if a congestion of two is allowed, i.e., each edge is allowed to be used in at most two of the paths.

In this paper, we give a randomized O(n^3/7 • poly (log n))-approximation algorithm with congestion two. This is the first result that breaks the O(n^1/2)-approximation algorithm. In particular, we prove the following. 1. If we have a (randomized) polynomial time algorithm for finding Ω(OPT^1/p) edge-disjoint paths for some p>1, then, for some α >0, we can give a randomized O(n^1/2-α)-approximation algorithm for the maximum edge-disjoint paths problem by using Rao-Zhou's algorithm. 2. Based on the well-linked set of Chekuri, Khanna, and Shepherd, we show that there is a randomized algorithm for finding Ω(OPT^1/4) edge-disjoint paths connecting given terminal pairs with congestion two.

Our framework for this algorithm is more general. Indeed, the above two ingredients also work for the maximum edge-disjoint paths problem (with congestion one) if the following conjecture is true. Conjecture: There is a (randomized) polynomial time algorithm for finding Ω(OPT^1/p/β(n)) edge-disjoint paths connecting given terminal pairs, where β is a poly-logarithmic function.

Supplementary Material

JPG File (stoc_2a_3.jpg)

Download
18.13 KB

MP4 File (stoc_2a_3.mp4)

Download
86.76 MB

References

[1]

. Andrews,Approximation algorithms for the edge-disjoint paths problem via Racke decompositions, Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS), 2010, 277--286.

Digital Library

[2]

. Andrews, J. Chuzhoy, S. Khanna and L. Zhang,Hardness of the undirected edge-disjoint paths problem with congestion. Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), 2005,226--244.

Digital Library

[3]

C. Chekuri, S. Khanna and B. Shepherd,The all-or-nothing multicommodity flow problem, Proc. 36th ACM Symposium on Theory of Computing (STOC), 2004, 156--165.

Digital Library

[4]

C. Chekuri, S. Khanna and B. Shepherd,Multicommodity flow, well-linked terminals, and routing problems, Proc. 37th ACM Symposium on Theory of Computing (STOC), 2005, 183--192.

Digital Library

[5]

C. Chekuri, S. Khanna and B. Shepherd,An O(√n) approximation and integrality gap for disjoint paths and unsplittable flow, Theory of computing, 2 (2006), 137--146.

[6]

. Diestel, Graph Theory, 3rd Edition, Springer-Verlag, 2005.

[7]

. Diestel, T.R. Jensen, K.Y. Gorbunov and C. Thomassen,Highly connected sets and the excluded grid theorem, J. Combin. Theory Ser. B, 75 (1999), 61--73.

Digital Library

[8]

S. Even, A. Itai and A. Shamir, On the complexity of timetable and multicommodity flow problems, SIAM Journal on Computing, 5 (1976), 691--703.

[9]

. Frank,Packing paths, cuts and circuits -- a survey,in Paths, Flows and VLSI-Layout,B. Korte, L. Lovász, H. J. Promel and A. Schrijver (Eds.),Springer-Verlag, Berlin, 1990, 49--100.

[10]

. Guruswami, S. Khanna, R. Rajaraman, B. Shepherd, and M. Yannakakis,Near-optimal hardness results and approximaiton algorithms for edge-disjoint paths andrelated problems, J. Comp. Syst. Science, 67 (2003), 473--496.Also, Proc. 31st ACM Symposium on Theory of Computing (STOC), 1999, 19--28.

Digital Library

[11]

. Kawarabayashi and B. Reed,A nearly linear time algorithm for the half integral disjoint paths packing, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008, 446--454.

Digital Library

[12]

. Kawarabayashi and Y. Kobayashi, Improved algorithm for the half-disjoint paths problem, Proc. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2010, 287--297.

Digital Library

[13]

. Kawarabayashi and Y. Kobayashi, An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs, Proc. 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2010, 274--286.

Digital Library

[14]

. Kawarabayashi, Y. Kobayashi and B. Reed,The disjoint paths problem in quadratic time, submitted.Available at http://research.nii.ac.jp/k_keniti/quaddp1.pdf.

[15]

. Kleinberg,Decision algorithms for unsplittable flow and the half-disjointpaths problem, Proc. 30th ACM Symposium on Theory of Computing (STOC), 1998,530--539.

Digital Library

[16]

. Kleinberg,An approximation algorithm for the disjoint paths problem in even-degree planar graphs, Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS), 2005, 627--636.

Digital Library

[17]

. Kleinberg and É. Tardos,Disjoint paths in densely embedded graphs, Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS), 1995, 52--61.

Digital Library

[18]

. Kleinberg and É. Tardos,Approximations for the disjoint paths problem in high-diameter planar networks, Proc. 27th ACM Symposium on Theory of Computing (STOC), 1995, 26--35.

Digital Library

[19]

. Kolliopoulos and C. Stein,Improved approximation algorithms for unsplittable flow problems, Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS), 1997, 426--435.

Digital Library

[20]

M.R. Kramer and J. van Leeuwen,The complexity of wire-routing and finding minimum area layouts for arbitrary VLSI circuits, Adv. Comput. Res., 2 (1984), 129--146.

[21]

. Kreutzer and S. Tazari,On brambles, grid-like minors, and parameterized intractability of monadicsecond-order logic, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, 354--364.

Digital Library

[22]

. Raghavan and C.D. Thompson,Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 7 (1987), 365--374.

Digital Library

[23]

. Rao and S. Zhou,Edge disjoint paths in moderately connected graphs, SIAM J. Computing, 39 (2010), 1856--1887.

Digital Library

[24]

. Reed,Tree width and tangles: A new connectivity measure and some applications,in Surveys in Combinatorics,London Math. Soc. Lecture Note Ser. 241,Cambridge Univ. Press, Cambridge, 1997, 87--162.

[25]

. Reed and D. Wood,Polynomial treewidth forces a large grid-like minor, availableat arXiv:0809.0724v3{math.CO}, 2008.

[26]

. Robertson and P.D. Seymour,Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), 65--110.

Digital Library

[27]

. Robertson, P.D. Seymour and R. Thomas,Quickly excluding a planar graph, J. Combin. Theory Ser. B, 62 (1994), 323--348.

Digital Library

[28]

. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, number 24 in Algorithm and Combinatorics, Springer-Verlag, 2003.

[29]

. Srinviasan,Improved approximations for edge-disjoint paths, unsplittable flow, andrelated routing problems, Proc. 38th IEEE Symposium on Foundations of Computer Science (FOCS), 1997, 416--425.

Digital Library

Cited By

Kawarabayashi KKobayashi Y(2016)An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion TwoACM Transactions on Algorithms10.1145/296041013:1(1-17)Online publication date: 21-Sep-2016
https://dl.acm.org/doi/10.1145/2960410
Chuzhoy JLi S(2016)A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2Journal of the ACM10.1145/289347263:5(1-51)Online publication date: 8-Nov-2016
https://dl.acm.org/doi/10.1145/2893472
Chekuri CEne AKhanna S(2013)Poly-logarithmic approximation for maximum node disjoint paths with constant congestionProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627841(326-341)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627841
Show More Cited By

Index Terms

Breaking o(n^1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Paths and connectivity problems

Recommendations

An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion Two

In the maximum edge-disjoint paths problem, we are given a graph and a collection of pairs of vertices, and the objective is to find the maximum number of pairs that can be routed by edge-disjoint paths. An r-approximation algorithm for this problem is ...
A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={ (s₁,t₁),… ,(s_k,t_k) } of pairs of vertices called demand pairs, and an integer c. The goal is to connect the maximum possible number ...
On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '11: Proceedings of the forty-third annual ACM symposium on Theory of computing

June 2011

840 pages

ISBN:9781450306911

DOI:10.1145/1993636

General Chair:
Lance Fortnow
Northwestern University
,
Program Chair:
Salil Vadhan
Harvard University

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'11

Sponsor:

SIGACT

STOC'11: Symposium on Theory of Computing

June 6 - 8, 2011

California, San Jose, USA

Acceptance Rates

STOC '11 Paper Acceptance Rate 84 of 304 submissions, 28%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
570
Total Downloads

Downloads (Last 12 months)63
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kawarabayashi KKobayashi Y(2016)An Improved Approximation Algorithm for the Edge-Disjoint Paths Problem with Congestion TwoACM Transactions on Algorithms10.1145/296041013:1(1-17)Online publication date: 21-Sep-2016
https://dl.acm.org/doi/10.1145/2960410
Chuzhoy JLi S(2016)A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2Journal of the ACM10.1145/289347263:5(1-51)Online publication date: 8-Nov-2016
https://dl.acm.org/doi/10.1145/2893472
Chekuri CEne AKhanna S(2013)Poly-logarithmic approximation for maximum node disjoint paths with constant congestionProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627841(326-341)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627841
Chuzhoy JKarloff HPitassi T(2012)Routing in undirected graphs with constant congestionProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214054(855-874)Online publication date: 19-May-2012
https://dl.acm.org/doi/10.1145/2213977.2214054
Chuzhoy JLi S(2012)A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science10.1109/FOCS.2012.54(233-242)Online publication date: 20-Oct-2012
https://dl.acm.org/doi/10.1109/FOCS.2012.54

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents