Document Open Access Logo

An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes

Authors Ignasi Sau , Giannos Stamoulis, Dimitrios M. Thilikos

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.95.pdf
  • Filesize: 0.92 MB
  • 20 pages

Document Identifiers

Author Details

Ignasi Sau
  • LIRMM, Université de Montpellier, CNRS, France
Giannos Stamoulis
  • Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Greece
  • Inter-university Postgraduate Programme "Algorithms, Logic, and Discrete Mathematics" (ALMA), Athens, Greece
Dimitrios M. Thilikos
  • LIRMM, Université de Montpellier, CNRS, France

Funding

  • Sau, Ignasi: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010).
  • Thilikos, Dimitrios M.: Supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). Supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

Acknowledgements

We wish to thank the anonymous reviewers for their comments and remarks that improved the presentation of this paper. Moreover, we wish to thank Dániel Marx for his valuable comments and advise.

Cite AsGet BibTex

Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.95

Abstract

Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G⧵S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2^{poly(k)}n³ time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2^{poly(k)}n² time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Graph modification problems
  • irrelevant vertex technique
  • graph minors
  • parameterized algorithms

Metrics

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

Related Versions

References

  1. Isolde Adler, Frederic Dorn, Fedor V. Fomin, Ignasi Sau, and Dimitrios M. Thilikos. Faster parameterized algorithms for minor containment. Theoretical Computer Science, 412(50):7018-7028, 2011. URL: https://doi.org/10.1016/j.tcs.2011.09.015.
  2. Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proc. of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 641-650, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347153.
  3. Ernst Althaus and Sarah Ziegler. Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm. CoRR, abs/1912.09144, 2019. URL: http://arxiv.org/abs/1912.09144.
  4. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth. In Proc. of the 12th International Symposium on Parameterized and Exact Computation (IPEC), volume 89 of LIPIcs, pages 4:1-4:12, 2017. URL: https://doi.org/10.4230/LIPIcs.IPEC.2017.4.
  5. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary. In Proc. of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 951-970, 2020. URL: https://doi.org/10.1137/130947374.
  6. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. II. single-exponential algorithms. Theoretical Computer Science, 814:135-152, 2020. URL: https://doi.org/10.1016/j.tcs.2020.01.026.
  7. Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos. Hitting minors on bounded treewidth graphs. III. lower bounds. Journal of Computer and System Sciences, 109:56-77, 2020. URL: https://doi.org/10.1016/j.jcss.2019.11.002.
  8. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michal Pilipczuk. A c^k n 5-Approximation Algorithm for Treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. URL: https://doi.org/10.1137/130947374.
  9. Hans L. Bodlaender, Pinar Heggernes, and Daniel Lokshtanov. Graph modification problems (dagstuhl seminar 14071). Dagstuhl Reports, 4(2):38-59, 2014. URL: https://doi.org/10.4230/DagRep.4.2.38.
  10. Hans L. Bodlaender, Hirotaka Ono, and Yota Otachi. A faster parameterized algorithm for pseudoforest deletion. Discrete Applied Mathematics, 236:42-56, 2018. URL: https://doi.org/10.1016/j.dam.2017.10.018.
  11. Andries E. Brouwer and Henk Jan Veldman. Contractibility and NP-completeness. Journal of Graph Theory, 11(1):71-79, 1987. URL: https://doi.org/10.1002/jgt.3190110111.
  12. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theoretical Computer Science, 411:3736-3756, September 2010. URL: https://doi.org/10.1016/j.tcs.2010.06.026.
  13. Christophe Crespelle, Pål Grønås, Drange, Fedor V. Fomin, and Petr A. Golovach. A survey of parameterized algorithms and the complexity of edge modification. CoRR, abs/2001.06867, 2013. URL: http://arxiv.org/abs/2001.06867.
  14. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  15. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion. Algorithmica, 64(1):170-188, 2012. URL: https://doi.org/10.1007/s00453-011-9578-2.
  16. Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional parameters and local treewidth. SIAM Journal on Discrete Mathematics, 18(3):501-511, 2004. URL: https://doi.org/10.1137/S0895480103433410.
  17. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  18. Michael R. Fellows, Jan Kratochvíl, Matthias Middendorf, and Frank Pfeiffer. The complexity of induced minors and related problems. Algorithmica, 13(3):266-282, 1995. URL: https://doi.org/10.1007/BF01190507.
  19. Michael R. Fellows and Michael A. Langston. Nonconstructive tools for proving polynomial-time decidability. Journal of the ACM, 35(3):727-739, 1988. URL: https://doi.org/10.1145/44483.44491.
  20. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  21. Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Modification to planarity is fixed parameter tractable. In Proc. of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 126 of LIPIcs, pages 28:1-28:17, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.28.
  22. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In Proc. of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 470-479, 2012. URL: https://doi.org/10.1109/FOCS.2012.62.
  23. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Hitting Topological Minors is FPT. CoRR, abs/1904.02944, 2019. To appear in Proc. of the 52nd Annual ACM Symposium on Theory of Computing (STOC 2020). URL: http://arxiv.org/abs/1904.02944.
  24. Fedor V. Fomin, Saket Saurabh, and Neeldhara Misra. Graph modification problems: A modern perspective. In Proc. of the 9th International Frontiers in Algorithmics Workshop (FAW), volume 9130 of LNCS, pages 3-6, 2015. URL: https://doi.org/10.1007/978-3-319-19647-3_1.
  25. Michael R. Garey and David S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman and Co., San Francisco, 1979. Google Scholar
  26. Archontia C. Giannopoulou, Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. Uniform kernelization complexity of hitting forbidden minors. ACM Transactions on Algorithms, 13(3):35:1-35:35, 2017. URL: https://doi.org/10.1145/3029051.
  27. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  28. Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Proc. of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1802-1811, 2014. URL: https://doi.org/10.1137/1.9781611973402.130.
  29. Gwenaël Joret, Christophe Paul, Ignasi Sau, Saket Saurabh, and Stéphan Thomassé. Hitting and harvesting pumpkins. SIAM Journal on Discrete Mathematics, 28(3):1363-1390, 2014. URL: https://doi.org/10.1137/120883736.
  30. Ken-ichi Kawarabayashi. Planarity allowing few error vertices in linear time. In Proc. of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 639-648, 2009. URL: https://doi.org/10.1109/FOCS.2009.45.
  31. Ken-ichi Kawarabayashi and Yusuke Kobayashi. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. In Proc. of the 29th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 14 of LIPIcs, pages 278-289, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.278.
  32. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 2011. URL: https://doi.org/10.1016/j.jctb.2011.07.004.
  33. Ken-ichi Kawarabayashi, Robin Thomas, and Paul Wollan. A new proof of the flat wall theorem. Journal of Combinatorial Theory, Series B, 129:204-238, 2018. URL: https://doi.org/10.1016/j.jctb.2017.09.006.
  34. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Transactions on Algorithms, 12(2):21:1-21:41, 2016. URL: https://doi.org/10.1145/2797140.
  35. Eun Jung Kim, Maria J. Serna, and Dimitrios M. Thilikos. Data-compression for parametrized counting problems on sparse graphs. In Proc. of the 29th International Symposium on Algorithms and Computation (ISAAC), volume 123 of LIPIcs, pages 20:1-20:13, 2018. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.20.
  36. Tomasz Kociumaka and Marcin Pilipczuk. Faster deterministic feedback vertex set. Information Processing Letters, 114(10):556-560, 2014. URL: https://doi.org/10.1016/j.ipl.2014.05.001.
  37. Tomasz Kociumaka and Marcin Pilipczuk. Deleting Vertices to Graphs of Bounded Genus. Algorithmica, 81(9):3655-3691, 2019. URL: https://doi.org/10.1007/s00453-019-00592-7.
  38. Alexandr V. Kostochka. Lower bound of the Hadwiger number of graphs by their average degree. Combinatorica, 4:307-316, 1984. URL: https://doi.org/10.1007/BF02579141.
  39. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences, 20(2):219-230, 1980. URL: https://doi.org/10.1016/0022-0000(80)90060-4.
  40. Daniel Lokshtanov. Wheel-Free Deletion Is W[2]-Hard. In Proc. of the 3rd International Workshop on Parameterized and Exact Computation (IWPEC), volume 5018 of LNCS, pages 141-147, 2008. URL: https://doi.org/10.1007/978-3-540-79723-4_14.
  41. Dániel Marx and Ildikó Schlotter. Obtaining a planar graph by vertex deletion. Algorithmica, 62(3-4):807-822, 2012. URL: https://doi.org/10.1007/s00453-010-9484-z.
  42. Rolf Niedermeier. Invitation to fixed parameter algorithms, volume 31. Oxford University Press, 2006. URL: https://doi.org/10.1093/ACPROF:OSO/9780198566076.001.0001.
  43. Ljubomir Perkovic and Bruce Reed. An Improved Algorithm for Finding Tree Decompositions of Small Width. International Journal of Foundations of Computer Science, 11:365-371, January 2000. URL: https://doi.org/10.1142/S0129054100000247.
  44. Bruce Reed, Kaleigh Smith, and Adrian Vetta. Finding odd cycle transversals. Operations Research Letters, 32(4):299-301, 2004. URL: https://doi.org/10.1016/j.orl.2003.10.009.
  45. Neil Robertson and Paul D. Seymour. Graph Minors. XIII. The Disjoint Paths Problem. Journal of Combinatorial Theory, Series B, 63(1):65-110, 1995. URL: https://doi.org/10.1006/jctb.1995.1006.
  46. Neil Robertson and Paul D. Seymour. Graph Minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. URL: https://doi.org/10.1016/j.jctb.2004.08.001.
  47. Ignasi Sau, Gianos Stamoulis, and Dimitrios M. Thilikos. An FPT-algorithm for recognizing k-apices of minor-closed graph classes. CoRR, abs/2004.12692, 2020. URL: http://arxiv.org/abs/2004.12692.
  48. Roded Sharan. Graph Modification Problems and their Applications to Genomic Research. PhD thesis, Sackler Faculty of Exact Sciences, School of Computer Science, 2002. Google Scholar
  49. Dimitrios M. Thilikos. Graph minors and parameterized algorithm design. In The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, pages 228-256, 2012. Google Scholar
  50. Andrew Thomason. The extremal function for complete minors. Journal of Combinatorial Theory, Series B, 81(2):318-338, 2001. URL: https://doi.org/10.1006/jctb.2000.2013.
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