Document Open Access Logo

Fine-Grained Meta-Theorems for Vertex Integrity

Authors Michael Lampis , Valia Mitsou

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2021.34.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Model-Checking
  • Fine-grained complexity
  • Vertex Integrity

Metrics

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

Abstract

Vertex Integrity is a graph measure which sits squarely between two more well-studied notions, namely vertex cover and tree-depth, and that has recently gained attention as a structural graph parameter. In this paper we investigate the algorithmic trade-offs involved with this parameter from the point of view of algorithmic meta-theorems for First-Order (FO) and Monadic Second Order (MSO) logic. Our positive results are the following: (i) given a graph G of vertex integrity k and an FO formula ϕ with q quantifiers, deciding if G satisfies ϕ can be done in time 2^O(k²q + q log q) + n^O(1); (ii) for MSO formulas with q quantifiers, the same can be done in time 2^{2^O(k²+kq)} + n^O(1). Both results are obtained using kernelization arguments, which pre-process the input to sizes 2^O(k²)q and 2^O(k²+kq) respectively. 
The complexities of our meta-theorems are significantly better than the corresponding meta-theorems for tree-depth, which involve towers of exponentials. However, they are worse than the roughly 2^{O(kq)} and 2^{2^{O(k+q)}} complexities known for corresponding meta-theorems for vertex cover. To explain this deterioration we present two formula constructions which lead to fine-grained complexity lower bounds and establish that the dependence of our meta-theorems on k is best possible. More precisely, we show that it is not possible to decide FO formulas with q quantifiers in time 2^o(k²q), and that there exists a constant-size MSO formula which cannot be decided in time 2^{2^o(k²)}, both under the ETH. Hence, the quadratic blow-up in the dependence on k is unavoidable and vertex integrity has a complexity for FO and MSO logic which is truly intermediate between vertex cover and tree-depth.

Cite As Get BibTex

Michael Lampis and Valia Mitsou. Fine-Grained Meta-Theorems for Vertex Integrity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.34

Author Details

Michael Lampis
  • Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France
Valia Mitsou
  • Université de Paris, IRIF, CNRS, 75205, Paris, France

Funding

  • Lampis, Michael: Partially supported by ANR JCJC project "ASSK" (ANR-18-CE40-0025-01).

References

  1. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In ESA, volume 173 of LIPIcs, pages 14:1-14:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  2. Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (approximate) defective coloring. SIAM J. Discret. Math., 34(2):1084-1106, 2020. Google Scholar
  3. Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (meta) kernelization. J. ACM, 63(5):44:1-44:69, 2016. Google Scholar
  4. Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden. Subgraph isomorphism on graph classes that exclude a substructure. Algorithmica, 82(12):3566-3587, 2020. Google Scholar
  5. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking. In FOCS, pages 601-612. IEEE, 2020. Google Scholar
  6. Bruno Courcelle. The monadic second-order logic of graphs. I. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  7. Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst., 33(2):125-150, 2000. Google Scholar
  8. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. Anuj Dawar, Martin Grohe, Stephan Kreutzer, and Nicole Schweikardt. Approximation schemes for first-order definable optimisation problems. In LICS, pages 411-420. IEEE Computer Society, 2006. Google Scholar
  10. Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and approximability of parameterized max-csps. Algorithmica, 79(1):230-250, 2017. Google Scholar
  11. Pål Grønås Drange, Markus S. Dregi, and Pim van 't Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica, 76(4):1181-1202, 2016. Google Scholar
  12. Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. Solving integer linear programs with a small number of global variables and constraints. In Carles Sierra, editor, Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 607-613. ijcai.org, 2017. URL: https://doi.org/10.24963/ijcai.2017/85.
  13. Pavel Dvořák and Dusan Knop. Parameterized complexity of length-bounded cuts and multicuts. Algorithmica, 80(12):3597-3617, 2018. Google Scholar
  14. Zdenek Dvořák, Daniel Král, and Robin Thomas. Testing first-order properties for subclasses of sparse graphs. J. ACM, 60(5):36:1-36:24, 2013. Google Scholar
  15. Eduard Eiben, Robert Ganian, and Stefan Szeider. Meta-kernelization using well-structured modulators. Discret. Appl. Math., 248:153-167, 2018. Google Scholar
  16. Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, and Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth. Inf. Comput., 209(2):143-153, 2011. URL: https://doi.org/10.1016/j.ic.2010.11.026.
  17. Jirí Fiala, Petr A. Golovach, and Jan Kratochvíl. Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theor. Comput. Sci., 412(23):2513-2523, 2011. URL: https://doi.org/10.1016/j.tcs.2010.10.043.
  18. Markus Frick. Generalized model-checking over locally tree-decomposable classes. Theory Comput. Syst., 37(1):157-191, 2004. Google Scholar
  19. Markus Frick and Martin Grohe. Deciding first-order properties of locally tree-decomposable structures. J. ACM, 48(6):1184-1206, 2001. Google Scholar
  20. Markus Frick and Martin Grohe. The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Log., 130(1-3):3-31, 2004. Google Scholar
  21. Jakub Gajarský and Petr Hliněný. Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Methods Comput. Sci., 11(1), 2015. Google Scholar
  22. Robert Ganian. Improving vertex cover as a graph parameter. Discret. Math. Theor. Comput. Sci., 17(2):77-100, 2015. Google Scholar
  23. Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, and Patrice Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Log. Methods Comput. Sci., 15(1), 2019. Google Scholar
  24. Robert Ganian, Petr Hliněný, Jaroslav Nešetřil, Jan Obdržálek, Patrice Ossona de Mendez, and Reshma Ramadurai. When trees grow low: Shrubs and fast MSO1. In MFCS, volume 7464 of Lecture Notes in Computer Science, pages 419-430. Springer, 2012. Google Scholar
  25. Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On structural parameterizations of the bounded-degree vertex deletion problem. Algorithmica, 83(1):297-336, 2021. Google Scholar
  26. Robert Ganian and Jan Obdržálek. Expanding the expressive power of monadic second-order logic on restricted graph classes. In IWOCA, volume 8288 of Lecture Notes in Computer Science, pages 164-177. Springer, 2013. Google Scholar
  27. Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. On structural parameterizations of the edge disjoint paths problem. Algorithmica, 83(6):1605-1637, 2021. URL: https://doi.org/10.1007/s00453-020-00795-3.
  28. Robert Ganian, Friedrich Slivovsky, and Stefan Szeider. Meta-kernelization with structural parameters. J. Comput. Syst. Sci., 82(2):333-346, 2016. Google Scholar
  29. Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. In CIAC, volume 12701 of Lecture Notes in Computer Science, pages 271-285. Springer, 2021. Google Scholar
  30. Martin Grohe and Stephan Kreutzer. Methods for algorithmic meta theorems. Model Theoretic Methods in Finite Combinatorics, 558:181-206, 2011. Google Scholar
  31. Gregory Z. Gutin, Mark Jones, and Magnus Wahlström. The mixed chinese postman problem parameterized by pathwidth and treedepth. SIAM J. Discrete Math., 30(4):2177-2205, 2016. URL: https://doi.org/10.1137/15M1034337.
  32. Ararat Harutyunyan, Michael Lampis, and Nikolaos Melissinos. Digraph coloring and distance to acyclicity. In STACS, volume 187 of LIPIcs, pages 41:1-41:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  33. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
  34. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. Discret. Appl. Math., 264:90-117, 2019. Google Scholar
  35. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. Discrete Applied Mathematics, 2020. URL: https://doi.org/10.1016/j.dam.2020.03.052.
  36. Leon Kellerhals and Tomohiro Koana. Parameterized complexity of geodetic set. In IPEC, volume 180 of LIPIcs, pages 20:1-20:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  37. Dusan Knop, Martin Koutecký, Tomás Masarík, and Tomás Toufar. Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity. Log. Methods Comput. Sci., 15(4), 2019. Google Scholar
  38. Dusan Knop, Tomás Masarík, and Tomás Toufar. Parameterized complexity of fair vertex evaluation problems. In MFCS, volume 138 of LIPIcs, pages 33:1-33:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  39. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. URL: https://doi.org/10.1007/s00453-011-9554-x.
  40. Michael Lampis. Model checking lower bounds for simple graphs. Log. Methods Comput. Sci., 10(1), 2014. Google Scholar
  41. Michael Lampis. Minimum stable cut and treewidth. In ICALP, volume 198 of LIPIcs, pages 92:1-92:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  42. Michael Lampis and Valia Mitsou. Treewidth with a quantifier alternation revisited. In IPEC, volume 89 of LIPIcs, pages 26:1-26:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  43. Michal Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In MFCS, volume 6907 of Lecture Notes in Computer Science, pages 520-531. Springer, 2011. Google Scholar
  44. Stefan Szeider. Monadic second order logic on graphs with local cardinality constraints. ACM Trans. Comput. Log., 12(2):12:1-12:21, 2011. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact