License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.34
URN: urn:nbn:de:0030-drops-154674
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15467/
Lampis, Michael ;
Mitsou, Valia
Fine-Grained Meta-Theorems for Vertex Integrity
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 |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
