Maximum edge-disjoint paths in planar graphs with congestion 2

• 成果类型: Article
• 署名作者: Seguin-Charbonneau, Loic; Shepherd, F. Bruce
• 署名单位: University of British Columbia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01513-1
• 发表日期: 2021
• 页码: 295-317
• 关键词: approximation algorithms; FLOW

摘要

We study the maximum edge-disjoint path problem (medp) in planar graphs G = (V, E) with edge capacities u(e). We are given a set of terminal pairs si ti, i = 1, 2..., k and wish to find a maximum routable subset of demands. That is, a subset of demands that can be connected by a family of paths that use each edge at most u(e) times. It is well-known that there is an integrality gap of Omega(root n) for the natural LP relaxation, even in planar graphs (Garg-Vazirani-Yannakakis). We show that if every edge has capacity at least 2, then the integrality gap drops to a constant. This result is tight also in a complexity-theoretic sense: recent results of Chuzhoy-Kim-Nimavat show that it is unlikely that there is any polytime-solvable LP formulation for medp which has a constant integrality gap for planar graphs. Along the way, we introduce the concept of rooted clustering which we believe is of independent interest.