Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2

被引:21
作者
Seguin-Charbonneau, Loic [1 ]
Shepherd, F. Bruce [2 ,3 ]
机构
[1] Royal Mil Coll Saint Jean, Dept Sci, St Jean, PQ, Canada
[2] McGill Univ, Math & Stat, Montreal, PQ H3A 2T5, Canada
[3] Microsoft Res, Theory Grp, Redmond, WA 98052 USA
来源
2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011) | 2011年
关键词
Network flows; edge-disjoint paths; confluent flows; clustering; APPROXIMATION ALGORITHMS; FLOW;
D O I
10.1109/FOCS.2011.30
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the maximum edge-disjoint path problem (MEDP) in planar graphs. We are given a set of terminal pairs and wish to find a maximum routable subset of demands. That is, a subset of demands that can be connected by edge-disjoint paths. It is well-known that there is an integrality gap of order square root of the number of nodes for this problem even on a grid-like graph, and hence in planar graphs (Garg et al.). In contrast, Chekuri et al. show that for planar graphs, if LP is the optimal solution to the natural linear programming relaxation for MEDP, then there is a subset of size OPT over the logarithm of the number of nodes which is routable with congestion 2. Subsequently they showed that it is possible to get within a constant factor of the optimal solution with congestion 4 instead of 2. We strengthen this latter result to show that a constant approximation is possible also with congestion 2 (and this is tight via the integrality gap grid example). We use a basic framework from work by Chekuri et al. At the heart of their approach is a 2-phase algorithm that selects an Okamura-Seymour instance. Each of their phases incurs a factor 2 congestion. It is possible to reduce one of the phases to have congestion 1. In order to achieve an overall congestion 2, however, the two phases must share capacity more carefully. For the Phase 1 problem, we extract a problem called rooted clustering that appears to be an interesting problem class in itself.
引用
收藏
页码:200 / 209
页数:10
相关论文
共 50 条
[11]   The maximum edge-disjoint paths problem in bidirected trees [J].
Erlebach, T ;
Jansen, K .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2001, 14 (03) :326-355
[12]   AN APPROXIMATION ALGORITHM FOR FULLY PLANAR EDGE-DISJOINT PATHS [J].
Huang, Chien-Chung ;
Mari, Mathieu ;
Mathieu, Claire ;
Schewior, Kevin ;
Vygen, Jens .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (02) :752-769
[13]   An O(log n)-Approximation Algorithm for the Edge-Disjoint Paths Problem in Eulerian Planar Graphs [J].
Kawarabayashi, Ken-Ichi ;
Kobayashi, Yusuke .
ACM TRANSACTIONS ON ALGORITHMS, 2013, 9 (02)
[14]   Optimal construction of edge-disjoint paths in random graphs [J].
Broder, AZ ;
Frieze, AM ;
Suen, S ;
Upfal, E .
SIAM JOURNAL ON COMPUTING, 1998, 28 (02) :542-574
[15]   EXISTENCE AND CONSTRUCTION OF EDGE-DISJOINT PATHS ON EXPANDER GRAPHS [J].
BRODER, AZ ;
FRIEZE, AM ;
UPFAL, E .
SIAM JOURNAL ON COMPUTING, 1994, 23 (05) :976-989
[16]   On the complexity of the planar directed edge-disjoint paths problem [J].
Müller, D .
MATHEMATICAL PROGRAMMING, 2006, 105 (2-3) :275-288
[17]   On the complexity of the planar directed edge-disjoint paths problem [J].
Dirk Müller .
Mathematical Programming, 2006, 105 :275-288
[19]   A TIGHT LOWER BOUND FOR EDGE-DISJOINT PATHS ON PLANAR DAGS* [J].
Chitnis, Rajesh .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (02) :556-572
[20]   Edge-Disjoint Paths Revisited [J].
Chekuri, Chandra ;
Khanna, Sanjeev .
ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (04)