Abstract
We consider the approximability of the maximum edge-disjoint paths problem (MEDP) in undirected graphs, and in particular, the integrality gap of the natural multicommodity flow based relaxation for it. The integrality gap is known to be \(\Omega(\sqrt{n})\) even for planar graphs [11] due to a simple topological obstruction and a major focus, following earlier work [14], has been understanding the gap if some constant congestion is allowed. In planar graphs the integrality gap is O(1) with congestion 2 [19,5]. In general graphs, recent work has shown the gap to be O(polylog(n)) [8,9] with congestion 2. Moreover, the gap is Ω(logΩ(c) n) in general graphs with congestion c for any constant c ≥ 1 [1].
It is natural to ask for which classes of graphs does a constant-factor constant-congestion property hold. It is easy to deduce that for given constant bounds on the approximation and congestion, the class of “nice” graphs is minor-closed. Is the converse true? Does every proper minor-closed family of graphs exhibit a constant-factor constant-congestion bound relative to the LP relaxation? We conjecture that the answer is yes. One stumbling block has been that such bounds were not known for bounded treewidth graphs (or even treewidth 3). In this paper we give a polytime algorithm which takes a fractional routing solution in a graph of bounded treewidth and is able to integrally route a constant fraction of the LP solution’s value. Note that we do not incur any edge congestion. Previously this was not known even for series parallel graphs which have treewidth 2. The algorithm is based on a more general argument that applies to k-sums of graphs in some graph family, as long as the graph family has a constant-factor constant-congestion bound. We then use this to show that such bounds hold for the class of k-sums of bounded genus graphs.
A full version of this article is available at http://arxiv.org/abs/1303.4897
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485–520 (2010)
Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 71–80 (2004)
Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 183–192. ACM (2005)
Chekuri, C., Khanna, S., Shepherd, F.B.: An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing 2(7), 137–146 (2006)
Chekuri, C., Khanna, S., Shepherd, F.B.: Edge-disjoint paths in planar graphs with constant congestion. SIAM Journal on Computing 39, 281–301 (2009)
Chekuri, C., Khanna, S., Shepherd, F.B.: A note on multiflows and treewidth. Algorithmica 54(3), 400–412 (2009)
Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. Journal of Combinatorial Theory, Series B 103(2), 248–273 (2013)
Chuzhoy, J.: Routing in undirected graphs with constant congestion. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 855–874. ACM (2012)
Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In: Proc. of IEEE FOCS (2012)
Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science 10(2), 111–121 (1980)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and ℓ1-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)
Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 682–690. ACM, New York (1993)
Kleinberg, J., Tardos, E.: Approximations for the disjoint paths problem in high-diameter planar networks. Journal of Computers and System Sciences 57(1), 61–73 (1998)
Lee, J.R., Sidiropoulos, A.: Genus and the geometry of the cut graph. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 193–201. Society for Industrial and Applied Mathematics (2010)
Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Journal of the ACM 46(6), 787–832 (1999)
Robertson, N., Seymour, P.D.: Graph minors: a survey. Surveys in Combinatorics 103, 153–171 (1985)
Robertson, N., Seymour, P.D.: Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B 89(1), 43–76 (2003)
Seguin-Charbonneau, L., Shepherd, F.B.: Maximum edge-disjoint paths in planar graphs with congestion 2. In: Proc. of IEEE FOCS, pp. 200–209 (2011)
Shmoys, D.: Cut problems and their application to divide-and-conquer. In: Approximation Algorithms for NP-Hard Problems. PWS series in computer science. PWS Pub. Co. (1997)
Tardos, É., Vazirani, V.V.: Improved bounds for the max-flow min-multicut ratio for planar and K r,r -free graphs. Information Processing Letters 47(2), 77–80 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chekuri, C., Naves, G., Shepherd, F.B. (2013). Maximum Edge-Disjoint Paths in k-Sums of Graphs. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)