Document Open Access Logo

Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs

Authors Chandra Chekuri, Alina Ene, Marcin Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.7.pdf
  • Filesize: 0.6 MB
  • 14 pages

Document Identifiers

Author Details

Chandra Chekuri
Alina Ene
Marcin Pilipczuk

Cite AsGet BibTex

Chandra Chekuri, Alina Ene, and Marcin Pilipczuk. Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.7

Abstract

We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph G = (V, E) and a collection of k source-destination pairs M = {s_1t_1, ..., s_kt_k}. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair s_it_i is routed in the symmetric setting if there is a directed path connecting s_i to t_i and a directed path connecting t_i to s_i. In this paper we obtain a randomized poly-logarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth h contains a constant congestion crossbar of size Omega(h/polylog(h)).
Keywords
  • Disjoint paths
  • symmetric demands
  • planar directed graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. M. Andrews. Approximation algorithms for the edge-disjoint paths problem via Raecke decompositions. In Proc. of IEEE FOCS, pages 277-286, 2010. Google Scholar
  2. M. Andrews, J. Chuzhoy, V. Guruswami, S. Khanna, K. Talwar, and L. Zhang. Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5):485-520, 2010. Google Scholar
  3. C. Chekuri and J. Chuzhoy. Large-treewidth graph decompositions and applications. In Proc. of ACM STOC, pages 291-300, 2013. Google Scholar
  4. C. Chekuri and J. Chuzhoy. Polynomial bounds for the grid-minor theorem. In Proc. of ACM STOC, pages 60-69, 2014. Google Scholar
  5. C. Chekuri and J. Chuzhoy. Degree-3 treewidth sparsifiers. In Proc. of ACM-SIAM SODA, pages 242-255, 2015. Google Scholar
  6. C. Chekuri and A. Ene. Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In Proc. of ACM-SIAM SODA, pages 326-341, 2013. Google Scholar
  7. C. Chekuri and A. Ene. The all-or-nothing flow problem in directed graphs with symmetric demand pairs. Mathematical Programming, pages 1-24, 2014. Google Scholar
  8. C. Chekuri, S. Khanna, and F.B. Shepherd. Multicommodity flow, well-linked terminals, and routing problems. In Proc. of ACM STOC, pages 183-192, 2005. Google Scholar
  9. C. Chekuri, S. Khanna, and F.B. Shepherd. An O(√n) approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137-146, 2006. Google Scholar
  10. Chandra Chekuri, Sreeram Kannan, Adnan Raja, and Pramod Viswanath. Multicommodity flows and cuts in polymatroidal networks. SIAM Journal on Computing, 44(4):912-943, 2015. Preliminary version in Proc. of ITCS, 2012. Google Scholar
  11. Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. The all-or-nothing multicommodity flow problem. SIAM Journal on Computing, 42(4):1467-1493, 2013. Preliminary version in Proc. of ACM STOC, 2004. Google Scholar
  12. J. Chen, Y. Liu, S. Lu, B. O'Sullivan, and I. Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM, 55(5), 2008. Google Scholar
  13. J. Chuzhoy. Routing in undirected graphs with constant congestion. In Proc. of ACM STOC, pages 855-874, 2012. Google Scholar
  14. J. Chuzhoy. Excluded grid theorem: Improved and simplified. In Proc. of ACM STOC, pages 645-654, 2015. Google Scholar
  15. J. Chuzhoy, V. Guruswami, S. Khanna, and K. Talwar. Hardness of routing with congestion in directed graphs. In Proc. of ACM STOC, pages 165-178, 2007. Google Scholar
  16. J. Chuzhoy, D.H.K. Kim, and S. Li. Improved approximation for node-disjoint paths in planar graphs. In Proc. of ACM STOC, 2016. To appear. Google Scholar
  17. J. Chuzhoy and S. Li. A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In Proc. of IEEE FOCS, 2012. Google Scholar
  18. M. Cygan, F. Fomin, L. Kowalik, D. Loksthanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2014. In print. Google Scholar
  19. E. D. Demaine and M. Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica, 28(1):19-36, 2008. Google Scholar
  20. P. Erdos and L. Pósa. On independent circuits contained in a graph. Canadian Journal of Mathematics, 17:347-352, 1965. Google Scholar
  21. G. Even, J. Naor, S. Rao, and B. Schieber. Divide-and-conquer approximation algorithms via spreading metrics. Journal of the ACM, 47(4):585-616, 2000. Google Scholar
  22. Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111-121, 1980. Google Scholar
  23. T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  24. T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Excluding a grid minor in digraphs. Manuscript, http://arxiv.org/abs/1510.00473, 2001.
  25. S. Kamath, S. Kannan, and P. Viswanath. Network capacity under traffic symmetry: Wireline and wireless networks. IEEE Transactions on Information Theory, 60(9):5457-5469, 2014. Google Scholar
  26. S. Kannan and P. Viswanath. Capacity of multiple unicast in wireless networks: A polymatroidal approach. IEEE Transactions on Information Theory, 60(10):6303-6328, 2014. Google Scholar
  27. K. Kawarabayashi and S. Kreutzer. An excluded grid theorem for digraphs with forbidden minors. In Proc. of ACM-SIAM SODA, pages 72-81, 2014. Google Scholar
  28. K. Kawarabayashi and S. Kreutzer. The directed grid theorem. In Proc. of ACM STOC, 2015. Google Scholar
  29. R. Khandekar, S. Rao, and U. Vazirani. Graph partitioning using single commodity flows. Journal of the ACM, 56(4):19, 2009. Google Scholar
  30. P. N. Klein, S.A. Plotkin, S. Rao, and E. Tardos. Approximation algorithms for Steiner and directed multicuts. Journal of Algorithms, 22(2):241-269, 1997. Google Scholar
  31. S. G. Kolliopoulos and C. Stein. Approximating disjoint-path problems using packing integer programs. Mathematical Programming, 99(1):63-87, 2004. Google Scholar
  32. A. Louis. Cut-matching games on directed graphs. CoRR, abs/1010.1047, 2010. Google Scholar
  33. S. Rao and S. Zhou. Edge disjoint paths in moderately connected graphs. SIAM Journal on Computing, 39(5):1856-1887, 2010. Google Scholar
  34. B. Reed. Introducing directed tree width. Electronic Notes in Discrete Mathematics, 3:222-229, 1999. Google Scholar
  35. B. Reed, N. Robertson, P. D. Seymour, and R. Thomas. Packing directed circuits. Combinatorica, 16(4):535-554, 1996. Google Scholar
  36. N. Robertson, P. D. Seymour, and R. Thomas. Quickly excluding a planar graph. Journal of Combinatorial Theory, Series B, 62(2):323-348, 1994. Google Scholar
  37. P. D. Seymour. Packing directed circuits fractionally. Combinatorica, 15(2):281-288, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact