skip to main content
research-article

Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

Published:31 January 2018Publication History
Skip Abstract Section

Abstract

Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker’s approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including Connected Dominating Set and Feedback Vertex Set. In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t× t grid as a minor guarantees that the treewidth of G is subquadratic in t. For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for “most” bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G ϵ G as input and an ϵ > 0, outputs a vertex set X of size ϵ ċ OPT such that the treewidth of G - X is f(ϵ). Here, OPT is the objective function value of the problem in question and f is a function depending only on ϵ. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems—including Cycle Packing, F-Packing, F-Deletion, Max Leaf Spanning Tree, or Partial r-Dominating Set —no EPTASs, even on planar graphs, were previously known.

We also prove novel excluded grid theorems in unit disk and map graphs without large cliques. Using these theorems, we show that these classes of graphs have the SQGM property. Based on the developed framework, we design EPTASs and subexponential time parameterized algorithms for various classes of problems on unit disk and map graphs.

References

  1. Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. 2002. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 4, 461--493.Google ScholarGoogle ScholarCross RefCross Ref
  2. Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. 2004. Polynomial-time data reduction for dominating set. Journal of the ACM 51, 3, 363--384. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Paola Alimonti and Viggo Kann. 2000. Some APX-completeness results for cubic graphs. Theoretical Computer Science 237, 1--2, 123--134. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Stefan Arnborg, Jens Lagergren, and Detlef Seese. 1991. Easy problems for tree-decomposable graphs. Journal of Algorithms 12, 2, 308--340. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. 2009. Expander flows, geometric embeddings and graph partitioning. Journal of the ACM 56, 2, 5:1--5:37. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Brenda S. Baker. 1994. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41, 1, 153--180. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Reuven Bar-Yehuda, Dan Geiger, Joseph Naor, and Ron M. Roth. 1998. Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference. SIAM Journal of Computing 27, 4, 942--959. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. 2016. (Meta) kernelization. Journal of the ACM 63, 5, 44:1--44:69. http://dl.acm.org/citation.cfm?id=2973749. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Richard B. Borie, R. Gary Parker, and Craig A. Tovey. 1992. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7, 5 and 6, 555--581.Google ScholarGoogle Scholar
  10. Sergio Cabello and David Gajser. 2015. Simple PTAS’s for families of graphs excluding a minor. Discrete Applied Mathematics 189, 41--48. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Timothy M. Chan. 2003. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms 46, 2, 178--189. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Timothy M. Chan and Sariel Har-Peled. 2012. Approximation algorithms for maximum independent set of pseudo-disks. Discrete 8 Computational Geometry 48, 2, 373--392.Google ScholarGoogle Scholar
  13. Chandra Chekuri and Julia Chuzhoy. 2016. Polynomial bounds for the grid-minor theorem. Journal of the ACM 63, 5, 40:1--40:65. http://dl.acm.org/citation.cfm?id=2820609. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Jianer Chen, Henning Fernau, Iyad A. Kanj, and Ge Xia. 2007. Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM Journal of Computing 37, 4, 1077--1106. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Z.-Z. Chen. 2001. Approximation algorithms for independent sets in map graphs. Journal of Algorithms 41, 20--40. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. Zhi-Zhong Chen, Enory Grigni, and Christos H. Papadimitriou. 1998. Planar map graphs. In Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC’98). ACM, 514--523. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Zhi-Zhong Chen, Enory Grigni, and Christos H. Papadimitriou. 2002. Map graphs. Journal of the ACM 49, 2, 127--138. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Julia Chuzhoy. 2016. Improved bounds for the excluded grid theorem. CoRR abs/1602.02629. (2016). http://arxiv.org/abs/1602.02629Google ScholarGoogle Scholar
  19. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. 1990. Unit disk graphs. Discrete Mathematics 86, 1--3, 165--177. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Bruno Courcelle. 1990. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation 85, 12--75. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Bruno Courcelle. 1997. The expression of graph properties and graph transformations in monadic second-order logic. Handbook of Graph Grammars and Computing by Graph Transformation. World Scientific Publishing Co., Inc. River Edge, NJ, USA, 313--400. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Dániel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer, New York, NY. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. 2006. Approximation schemes for first-order definable optimisation problems. Logic in Computer Science 411--420. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. 2005b. Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Transactions on Algorithms 1, 1, 33--47. Google ScholarGoogle ScholarDigital LibraryDigital Library
  25. Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. 2005a. Subexponential parameterized algorithms on graphs of bounded genus and -minor-free graphs. J. ACM 52, 6 (2005), 866--893. Google ScholarGoogle ScholarDigital LibraryDigital Library
  26. Erik D. Demaine and MohammadTaghi Hajiaghayi. 2005. Bidimensionality: New connections between FPT algorithms and PTASs. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). ACM-SIAM, 590--601. Google ScholarGoogle ScholarDigital LibraryDigital Library
  27. Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008a. Bidimensionality. In Encyclopedia of Algorithms, Ming-Yang Kao (ed.). Springer, New York, NY.Google ScholarGoogle Scholar
  28. Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008b. The bidimensionality theory and its algorithmic applications. The Computer Journal 51, 3, 292--302. Google ScholarGoogle ScholarDigital LibraryDigital Library
  29. Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008c. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28, 1 (2008), 19--36. Google ScholarGoogle ScholarDigital LibraryDigital Library
  30. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. 2009. Algorithmic graph minor theory: Improved grid minor bounds and Wagner’s contraction. Algorithmica 54, 2, 142--180. Google ScholarGoogle ScholarDigital LibraryDigital Library
  31. Reinhard Diestel. 2005. Graph Theory (3rd ed.). Springer-Verlag, Heidelberg.Google ScholarGoogle Scholar
  32. Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. 2008. Subexponential parameterized algorithms. Computer Science Review 2, 1, 29--39. Google ScholarGoogle ScholarDigital LibraryDigital Library
  33. Adrian Dumitrescu and János Pach. 2011. Minimum clique partition in unit disk graphs. Graphs and Combinatorics 27, 3, 399--411. Google ScholarGoogle ScholarDigital LibraryDigital Library
  34. Peter Eades, Antonios Symvonis, and Sue Whitesides. 2000. Three-dimensional orthogonal graph drawing algorithms. Discrete Applied Mathematics 103, 1--3, 55--87. Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. David Eisenstat, Philip Klein, and Claire Mathieu. 2012. An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 626--638. Google ScholarGoogle ScholarDigital LibraryDigital Library
  36. David Eppstein. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3, 1--27.Google ScholarGoogle ScholarCross RefCross Ref
  37. David Eppstein. 2000. Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275--291.Google ScholarGoogle ScholarCross RefCross Ref
  38. Thomas Erlebach, Klaus Jansen, and Eike Seidel. 2005. Polynomial-time approximation schemes for geometric intersection graphs. SIAM Journal on Computing 34, 6, 1302--1323. Google ScholarGoogle ScholarDigital LibraryDigital Library
  39. Uriel Feige, MohammadTaghi Hajiaghayi, and James R. Lee. 2008. Improved approximation algorithms for minimum weight vertex separators. SIAM Journal on Computing 38, 2, 629--657. Google ScholarGoogle ScholarDigital LibraryDigital Library
  40. Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. 2011. Contraction obstructions for treewidth. Journal of Combinatorial Theory Series B 101, 5, 302--314. Google ScholarGoogle ScholarDigital LibraryDigital Library
  41. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, M. S. Ramanujan, and Saket Saurabh. 2015. Solving d-SAT via backdoors to small treewidth. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’15). SIAM, 630--641. Google ScholarGoogle ScholarDigital LibraryDigital Library
  42. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012b. Planar F-deletion: Approximation, kernelization and optimal FPT algorithms. In Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS’12). IEEE, 470--479. Google ScholarGoogle ScholarDigital LibraryDigital Library
  43. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2017. Finding, hitting and packing cycles in subexponential time on unit disk graphs. In Proceedings of the 44th International Colloquium of Automata, Languages and Programming (ICALP’17) (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 65:1--65:15.Google ScholarGoogle Scholar
  44. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. 2011a. Bidimensionality and EPTAS. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’11). SIAM, 748--759. Google ScholarGoogle ScholarDigital LibraryDigital Library
  45. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. 2011b. Subexponential algorithms for partial cover problems. Information Processing Letters 111, 16, 814--818. Google ScholarGoogle ScholarDigital LibraryDigital Library
  46. Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. 2012a. Bidimensionality and geometric graphs. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). SIAM, 1563--1575. Google ScholarGoogle ScholarDigital LibraryDigital Library
  47. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. 2010. Bidimensionality and kernels. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’10). SIAM, 503--510. Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. Fedor V. Fomin and Dimitrios M. Thilikos. 2006. New upper bounds on the decomposability of planar graphs. Journal of Graph Theory 51, 1, 53--81. Google ScholarGoogle ScholarDigital LibraryDigital Library
  49. Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. 2004. Approximation algorithms for partial covering problems. Journal of Algorithms 53, 1, 55--84. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. Martin Grohe. 2003. Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23, 4, 613--632. Google ScholarGoogle ScholarDigital LibraryDigital Library
  51. Qianping Gu and Gengchun Xu. 2014. Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs. CoRR abs/1407.6761. http://arxiv.org/abs/1407.6761.Google ScholarGoogle Scholar
  52. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. 2010. Fixed-parameter tractability results for full-degree spanning tree and its dual. Networks 56, 2, 116--130. Google ScholarGoogle ScholarDigital LibraryDigital Library
  53. Sariel Har-Peled and Kent Quanrud. 2015. Approximation algorithms for polynomial-expansion and low-density graphs. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, Vol. 9294. Springer, Berlin, 717--728.Google ScholarGoogle Scholar
  54. Dorit S. Hochbaum and Wolfgang Maass. 1985. Approximation schemes for covering and packing problems in image processing and VLSI. Journal of the ACM 32, 1, 130--136. Google ScholarGoogle ScholarDigital LibraryDigital Library
  55. Harry B. Hunt, III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, and Richard E. Stearns. 1998. NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms 26, 2, 238--274. Google ScholarGoogle ScholarDigital LibraryDigital Library
  56. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity. Journal of Computer and System Sciences 63, 4, 512--530. Google ScholarGoogle ScholarDigital LibraryDigital Library
  57. Bart M. P. Jansen. 2010. Polynomial kernels for hard problems on disk graphs. In Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’10), Lecture Notes in Comput. Science, Vol. 6139. Springer, Berlin, 310--321. Google ScholarGoogle ScholarDigital LibraryDigital Library
  58. G. A. Kabatiansky and V. I. Levenshtein. 1978. Bounds for packings on a sphere and in space. Problemy Peredachi Informatsii 14, 3--25.Google ScholarGoogle Scholar
  59. Sanjeev Khanna and Rajeev Motwani. 1996. Towards a syntactic characterization of PTAS. In STOC’96. ACM, 329--337. Google ScholarGoogle ScholarDigital LibraryDigital Library
  60. Philip N. Klein and Dániel Marx. 2014. A subexponential parameterized algorithm for Subset TSP on planar graphs. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14). SIAM, 1812--1830. Google ScholarGoogle ScholarDigital LibraryDigital Library
  61. Jon M. Kleinberg and Amit Kumar. 2001. Wavelength conversion in optical networks. Journal of Algorithms 38, 1, 25--50. Google ScholarGoogle ScholarDigital LibraryDigital Library
  62. Daniel J. Kleitman and Douglas B. West. 1991. Spanning trees with many leaves. SIAM Journal on Discrete Mathematics 4, 1, 99--106. Google ScholarGoogle ScholarDigital LibraryDigital Library
  63. Richard J. Lipton and Robert Endre Tarjan. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177--189.Google ScholarGoogle ScholarDigital LibraryDigital Library
  64. Richard J. Lipton and Robert Endre Tarjan. 1980. Applications of a planar separator theorem. SIAM Journal on Computing 9, 615--627.Google ScholarGoogle ScholarDigital LibraryDigital Library
  65. M. V. Marathe, H. Breu, H. B. Hunt, III, S. S. Ravi, and D. J. Rosenkrantz. 1995. Simple heuristics for unit disk graphs. Networks 25, 2, 59--68.Google ScholarGoogle ScholarCross RefCross Ref
  66. Dániel Marx. 2008. Parameterized complexity and approximation algorithms. The Computer Journal 51, 1, 60--78. Google ScholarGoogle ScholarDigital LibraryDigital Library
  67. Dániel Marx. 2013. The square root phenomenon in planar graphs. In Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP’13), Lecture Notes in Computer Science, Vol. 7966. Springer, Berlin, 28. Google ScholarGoogle ScholarDigital LibraryDigital Library
  68. Gary L. Miller, Shang-Hua Teng, William P. Thurston, and Stephen A. Vavasis. 1997. Separators for sphere-packings and nearest neighbor graphs. Journal of the ACM 44, 1, 1--29. Google ScholarGoogle ScholarDigital LibraryDigital Library
  69. Hannes Moser. 2005. Exact Algorithms for Generalizations of Vertex Cover. Master’s thesis. Institut für Informatik, Friedrich-Schiller-Universität, Jena, Thuringia, Germany.Google ScholarGoogle Scholar
  70. Nabil H. Mustafa and Saurabh Ray. 2010. Improved results on geometric hitting set problems. Discrete 8 Computational Geometry 44, 4, 883--895.Google ScholarGoogle Scholar
  71. George L. Nemhauser and Leslie E. Trotter, Jr. 1974. Properties of vertex packing and independence system polyhedra. Mathematical Programming 6, 48--61. Google ScholarGoogle ScholarDigital LibraryDigital Library
  72. Vijay Raghavan and Jeremy Spinrad. 2003. Robust algorithms for restricted domains. Journal of Algorithms 48, 1, 160--172. Google ScholarGoogle ScholarDigital LibraryDigital Library
  73. Neil Robertson and Paul D. Seymour. 1984. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory Series B 36, 49--64.Google ScholarGoogle ScholarCross RefCross Ref
  74. Neil Robertson and Paul D. Seymour. 1991. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory Series B 52, 2, 153--190. Google ScholarGoogle ScholarDigital LibraryDigital Library
  75. Neil Robertson, Paul D. Seymour, and Robin Thomas. 1994. Quickly excluding a planar graph. Journal of Combinatorial Theory Series B 62, 323--348. Google ScholarGoogle ScholarDigital LibraryDigital Library
  76. Paul D. Seymour and Robin Thomas. 1993. Graph searching and a minimax theorem for tree-width. Journal of Combinatorial Theory Series B 58, 239--257. Google ScholarGoogle ScholarDigital LibraryDigital Library
  77. Mikkel Thorup. 1998. Map graphs in polynomial time. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS’98). IEEE Computer Society, 396--405. Google ScholarGoogle ScholarDigital LibraryDigital Library
  78. Erik Jan van Leeuwen. 2009. Optimization and Approximation on Systems of Geometric Objects. Ph.D. Dissertation. De Vries Instituut, Amsterdam, The Netherlands.Google ScholarGoogle Scholar

Index Terms

  1. Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in

      Full Access

      • Published in

        cover image Journal of the ACM
        Journal of the ACM  Volume 65, Issue 2
        April 2018
        244 pages
        ISSN:0004-5411
        EISSN:1557-735X
        DOI:10.1145/3184466
        Issue’s Table of Contents

        Copyright © 2018 ACM

        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 31 January 2018
        • Accepted: 1 October 2017
        • Revised: 1 May 2017
        • Received: 1 May 2016
        Published in jacm Volume 65, Issue 2

        Permissions

        Request permissions about this article.

        Request Permissions

        Check for updates

        Qualifiers

        • research-article
        • Research
        • Refereed

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader