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.
- 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 ScholarCross Ref
- 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 ScholarDigital Library
- Paola Alimonti and Viggo Kann. 2000. Some APX-completeness results for cubic graphs. Theoretical Computer Science 237, 1--2, 123--134. Google ScholarDigital Library
- Stefan Arnborg, Jens Lagergren, and Detlef Seese. 1991. Easy problems for tree-decomposable graphs. Journal of Algorithms 12, 2, 308--340. Google ScholarDigital Library
- 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 ScholarDigital Library
- Brenda S. Baker. 1994. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41, 1, 153--180. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- Sergio Cabello and David Gajser. 2015. Simple PTAS’s for families of graphs excluding a minor. Discrete Applied Mathematics 189, 41--48. Google ScholarDigital Library
- Timothy M. Chan. 2003. Polynomial-time approximation schemes for packing and piercing fat objects. Journal of Algorithms 46, 2, 178--189. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Z.-Z. Chen. 2001. Approximation algorithms for independent sets in map graphs. Journal of Algorithms 41, 20--40. Google ScholarDigital Library
- 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 ScholarDigital Library
- Zhi-Zhong Chen, Enory Grigni, and Christos H. Papadimitriou. 2002. Map graphs. Journal of the ACM 49, 2, 127--138. Google ScholarDigital Library
- Julia Chuzhoy. 2016. Improved bounds for the excluded grid theorem. CoRR abs/1602.02629. (2016). http://arxiv.org/abs/1602.02629Google Scholar
- Brent N. Clark, Charles J. Colbourn, and David S. Johnson. 1990. Unit disk graphs. Discrete Mathematics 86, 1--3, 165--177. Google ScholarDigital Library
- Bruno Courcelle. 1990. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation 85, 12--75. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008a. Bidimensionality. In Encyclopedia of Algorithms, Ming-Yang Kao (ed.). Springer, New York, NY.Google Scholar
- Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008b. The bidimensionality theory and its algorithmic applications. The Computer Journal 51, 3, 292--302. Google ScholarDigital Library
- Erik D. Demaine and MohammadTaghi Hajiaghayi. 2008c. Linearity of grid minors in treewidth with applications through bidimensionality. Combinatorica 28, 1 (2008), 19--36. Google ScholarDigital Library
- 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 ScholarDigital Library
- Reinhard Diestel. 2005. Graph Theory (3rd ed.). Springer-Verlag, Heidelberg.Google Scholar
- Frederic Dorn, Fedor V. Fomin, and Dimitrios M. Thilikos. 2008. Subexponential parameterized algorithms. Computer Science Review 2, 1, 29--39. Google ScholarDigital Library
- Adrian Dumitrescu and János Pach. 2011. Minimum clique partition in unit disk graphs. Graphs and Combinatorics 27, 3, 399--411. Google ScholarDigital Library
- Peter Eades, Antonios Symvonis, and Sue Whitesides. 2000. Three-dimensional orthogonal graph drawing algorithms. Discrete Applied Mathematics 103, 1--3, 55--87. Google ScholarDigital Library
- 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 ScholarDigital Library
- David Eppstein. 1999. Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications 3, 1--27.Google ScholarCross Ref
- David Eppstein. 2000. Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275--291.Google ScholarCross Ref
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Rajiv Gandhi, Samir Khuller, and Aravind Srinivasan. 2004. Approximation algorithms for partial covering problems. Journal of Algorithms 53, 1, 55--84. Google ScholarDigital Library
- Martin Grohe. 2003. Local tree-width, excluded minors, and approximation algorithms. Combinatorica 23, 4, 613--632. Google ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- G. A. Kabatiansky and V. I. Levenshtein. 1978. Bounds for packings on a sphere and in space. Problemy Peredachi Informatsii 14, 3--25.Google Scholar
- Sanjeev Khanna and Rajeev Motwani. 1996. Towards a syntactic characterization of PTAS. In STOC’96. ACM, 329--337. Google ScholarDigital Library
- 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 ScholarDigital Library
- Jon M. Kleinberg and Amit Kumar. 2001. Wavelength conversion in optical networks. Journal of Algorithms 38, 1, 25--50. Google ScholarDigital Library
- Daniel J. Kleitman and Douglas B. West. 1991. Spanning trees with many leaves. SIAM Journal on Discrete Mathematics 4, 1, 99--106. Google ScholarDigital Library
- Richard J. Lipton and Robert Endre Tarjan. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177--189.Google ScholarDigital Library
- Richard J. Lipton and Robert Endre Tarjan. 1980. Applications of a planar separator theorem. SIAM Journal on Computing 9, 615--627.Google ScholarDigital Library
- 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 ScholarCross Ref
- Dániel Marx. 2008. Parameterized complexity and approximation algorithms. The Computer Journal 51, 1, 60--78. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- Nabil H. Mustafa and Saurabh Ray. 2010. Improved results on geometric hitting set problems. Discrete 8 Computational Geometry 44, 4, 883--895.Google Scholar
- George L. Nemhauser and Leslie E. Trotter, Jr. 1974. Properties of vertex packing and independence system polyhedra. Mathematical Programming 6, 48--61. Google ScholarDigital Library
- Vijay Raghavan and Jeremy Spinrad. 2003. Robust algorithms for restricted domains. Journal of Algorithms 48, 1, 160--172. Google ScholarDigital Library
- Neil Robertson and Paul D. Seymour. 1984. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory Series B 36, 49--64.Google ScholarCross Ref
- 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 ScholarDigital Library
- Neil Robertson, Paul D. Seymour, and Robin Thomas. 1994. Quickly excluding a planar graph. Journal of Combinatorial Theory Series B 62, 323--348. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Erik Jan van Leeuwen. 2009. Optimization and Approximation on Systems of Geometric Objects. Ph.D. Dissertation. De Vries Instituut, Amsterdam, The Netherlands.Google Scholar
Index Terms
Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes
Recommendations
Bidimensionality and geometric graphs
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithmsBidimensionality theory was introduced by Demaine et al. [JACM 2005] as a framework to obtain algorithmic results for hard problems on minor closed graph classes. The theory has been successfully applied to yield subex-ponential time parameterized ...
Polynomial time approximation schemes and parameterized complexity
In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP ...
Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction
We explore three important avenues of research in algorithmic graph-minor theory, which all stem from a key min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of ...
Comments