Document Open Access Logo

Subexponential Parameterized Algorithms for Graphs of Polynomial Growth

Authors Dániel Marx, Marcin Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.59.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Dániel Marx
Marcin Pilipczuk

Cite As Get BibTex

Dániel Marx and Marcin Pilipczuk. Subexponential Parameterized Algorithms for Graphs of Polynomial Growth. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.59

Abstract

We show that for a number of parameterized problems for which only  2^{O(k)} n^{O(1)} time algorithms are known on general graphs, subexponential parameterized algorithms with running time 2^{O(k^{1-1/(1+d)} log^2 k)} n^{O(1)} are possible for graphs of polynomial growth with growth rate (degree) d, that is, if we assume that every ball of radius r contains only O(r^d) vertices. The algorithms use the technique of low-treewidth pattern covering, introduced by Fomin et al. [FOCS 2016] for planar graphs; here we show how this strategy can be made to work for graphs of polynomial growth.

Formally, we prove that, given a graph G of polynomial growth with growth rate d and an integer k, one can in randomized polynomial time find a subset A of V(G) such that on one hand the treewidth of G[A] is O(k^{1-1/(1+d)} log k), and on the other hand for every set X of vertices of size at most k, the probability that X is a subset of A is 2^{-O(k^{1-1/(1+d)} log^2 k)}.  Together with standard dynamic programming techniques on graphs of bounded treewidth, this statement gives subexponential parameterized algorithms for a number of subgraph search problems, such as Long Path or Steiner Tree, in graphs of polynomial growth.

We complement the algorithm with an almost tight lower bound for Long Path: unless the Exponential Time Hypothesis fails, no parameterized algorithm with running time 2^{k^{1-1/d-epsilon}}n^{O(1)} is possible for any positive epsilon and any integer d >= 3.

Subject Classification

Keywords
  • polynomial growth
  • subexponential algorithm
  • low treewidth pattern covering

Metrics

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

References

  1. Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. In 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 4-7 July 2006, Lisboa, Portugal, page 75. IEEE Computer Society, 2006. URL: http://dx.doi.org/10.1109/ICDCS.2006.72.
  2. Ittai Abraham and Dahlia Malkhi. Name independent routing for growth bounded networks. In Phillip B. Gibbons and Paul G. Spirakis, editors, SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 18-20, 2005, Las Vegas, Nevada, USA, pages 49-55. ACM, 2005. URL: http://dx.doi.org/10.1145/1073970.1073978.
  3. Yair Bartal. On approximating arbitrary metrices by tree metrics. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 161-168. ACM, 1998. URL: http://dx.doi.org/10.1145/276698.276725.
  4. Vincent Blondel, Kyomin Jung, Pushmeet Kohli, and Devavrat Shah. Partition-merge: Distributed inference and modularity optimization. CoRR, abs/1309.6129, 2013. URL: http://arxiv.org/abs/1309.6129.
  5. T. H. Hubert Chan. Approximation Algorithms for Bounded Dimensional Metric Spaces. PhD thesis, Carnagie Mellon University, 2007. Available at URL: http://i.cs.hku.hk/~hubert/thesis/thesis.pdf.
  6. Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, and Serge A. Plotkin. Approximating a finite metric by a small number of tree metrics. In 39th Annual Symposium on Foundations of Computer Science, FOCS'98, November 8-11, 1998, Palo Alto, California, USA, pages 379-388. IEEE Computer Society, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743488.
  7. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. Tight bounds for Planar Strongly Connected Steiner Subgraph with fixed number of terminals (and extensions). In SODA 2014, pages 1782-1801, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.129.
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  9. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional parameters and local treewidth. SIAM J. Discrete Math., 18(3):501-511, 2004. URL: http://dx.doi.org/10.1137/S0895480103433410.
  10. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Fixed-parameter algorithms for (k,r)-Center in planar graphs and map graphs. ACM Transactions on Algorithms, 1(1):33-47, 2005. URL: http://dx.doi.org/10.1145/1077464.1077468.
  11. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  12. Erik D. Demaine and Mohammad Taghi Hajiaghayi. Fast algorithms for hard graph problems: Bidimensionality, minors, and local treewidth. In Graph Drawing, pages 517-533, 2004. URL: http://dx.doi.org/10.1007/978-3-540-31843-9_57.
  13. Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. Comput. J., 51(3):292-302, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm033.
  14. Erik D. Demaine and MohammadTaghi Hajiaghayi. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica, 28(1):19-36, 2008. URL: http://dx.doi.org/10.1007/s00493-008-2140-4.
  15. Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Beyond bidimensionality: Parameterized subexponential algorithms on directed graphs. In STACS 2010, pages 251-262, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2459.
  16. Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. Subexponential parameterized algorithms. Computer Science Review, 2(1):29-39, 2008. URL: http://dx.doi.org/10.1016/j.cosrev.2008.02.004.
  17. Frederic Dorn, Eelko Penninkx, Hans L. Bodlaender, and Fedor V. Fomin. Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790-810, 2010. URL: http://dx.doi.org/10.1007/s00453-009-9296-1.
  18. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering. In FOCS, pages 515-524, 2016. Full version available at URL: http://arxiv.org/abs/1604.05999.
  19. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Subexponential algorithms for partial cover problems. Inf. Process. Lett., 111(16):814-818, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.05.016.
  20. Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput., 36(2):281-309, 2006. URL: http://dx.doi.org/10.1137/S0097539702419649.
  21. Ramakrishna Gummadi, Kyomin Jung, Devavrat Shah, and Ramavarapu S. Sreenivas. Computing the capacity region of a wireless network. In INFOCOM 2009. 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 19-25 April 2009, Rio de Janeiro, Brazil, pages 1341-1349. IEEE, 2009. URL: http://dx.doi.org/10.1109/INFCOM.2009.5062049.
  22. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  23. Philip N. Klein and Dániel Marx. Solving planar k-terminal cut in O(n^c √k) time. In Proceedings of the 39th International Colloquium of Automata, Languages and Programming (ICALP), volume 7391 of Lecture Notes in Comput. Sci., pages 569-580. Springer, 2012. Google Scholar
  24. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs. In SODA 2014, pages 1812-1830, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.131.
  25. Nathan Linial and Michael E. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441-454, 1993. URL: http://dx.doi.org/10.1007/BF01303516.
  26. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of the EATCS, 105:41-72, 2011. URL: http://albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.
  27. Dániel Marx and Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In Siu-Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry, SOCG'14, Kyoto, Japan, June 08-11, 2014, page 67. ACM, 2014. URL: http://dx.doi.org/10.1145/2582112.2582124.
  28. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-27875-4.
  29. Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Subexponential-time parameterized algorithm for Steiner Tree on planar graphs. In STACS 2013, pages 353-364, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2013.353.
  30. Marcin Pilipczuk, Michał Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Network sparsification for Steiner problems on planar and bounded-genus graphs. In FOCS 2014, pages 276-285. IEEE Computer Society, 2014. Google Scholar
  31. Dimitrios M. Thilikos. Fast sub-exponential algorithms and compactness in planar graphs. In ESA 2011, pages 358-369, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_31.
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 About DROPS Imprint Privacy Contact