Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Lampis, Michael; Mitsou, Valia https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-154674
URL:

;

Fine-Grained Meta-Theorems for Vertex Integrity

pdf-format:


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.

BibTeX - Entry

@InProceedings{lampis_et_al:LIPIcs.ISAAC.2021.34,
  author =	{Lampis, Michael and Mitsou, Valia},
  title =	{{Fine-Grained Meta-Theorems for Vertex Integrity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15467},
  URN =		{urn:nbn:de:0030-drops-154674},
  doi =		{10.4230/LIPIcs.ISAAC.2021.34},
  annote =	{Keywords: Model-Checking, Fine-grained complexity, Vertex Integrity}
}

Keywords: Model-Checking, Fine-grained complexity, Vertex Integrity
Seminar: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue date: 2021
Date of publication: 30.11.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI