Lampis, Michael ;
Mitsou, Valia
FineGrained MetaTheorems for Vertex Integrity
Abstract
Vertex Integrity is a graph measure which sits squarely between two more wellstudied notions, namely vertex cover and treedepth, and that has recently gained attention as a structural graph parameter. In this paper we investigate the algorithmic tradeoffs involved with this parameter from the point of view of algorithmic metatheorems for FirstOrder (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 preprocess the input to sizes 2^O(k²)q and 2^O(k²+kq) respectively.
The complexities of our metatheorems are significantly better than the corresponding metatheorems for treedepth, 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 metatheorems for vertex cover. To explain this deterioration we present two formula constructions which lead to finegrained complexity lower bounds and establish that the dependence of our metatheorems 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 constantsize MSO formula which cannot be decided in time 2^{2^o(k²)}, both under the ETH. Hence, the quadratic blowup 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 treedepth.
BibTeX  Entry
@InProceedings{lampis_et_al:LIPIcs.ISAAC.2021.34,
author = {Lampis, Michael and Mitsou, Valia},
title = {{FineGrained MetaTheorems for Vertex Integrity}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {34:134:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772143},
ISSN = {18688969},
year = {2021},
volume = {212},
editor = {Ahn, HeeKap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15467},
URN = {urn:nbn:de:0030drops154674},
doi = {10.4230/LIPIcs.ISAAC.2021.34},
annote = {Keywords: ModelChecking, Finegrained complexity, Vertex Integrity}
}
30.11.2021
Keywords: 

ModelChecking, Finegrained complexity, Vertex Integrity 
Seminar: 

32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Issue date: 

2021 
Date of publication: 

30.11.2021 