{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T20:35:02Z","timestamp":1770064502021,"version":"3.49.0"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2024,12,3]]},"abstract":"<jats:p>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 $\\phi$ with $q$ quantifiers, deciding if $G$ satisfies $\\phi$ can be done in time $2^{O(k^2q+q\\log q)}+n^{O(1)}$; (ii) for MSO formulas with $q$ quantifiers, the same can be done in time $2^{2^{O(k^2+kq)}}+n^{O(1)}$. Both results are obtained using kernelization arguments, which pre-process the input to sizes $2^{O(k^2)}q$ and $2^{O(k^2+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 the best possible. More precisely, we show that it is not possible to decide FO formulas with $q$ quantifiers in time $2^{o(k^2q)}$, and that there exists a constant-size MSO formula which cannot be decided in time $2^{2^{o(k^2)}}$, 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.<\/jats:p>","DOI":"10.46298\/lmcs-20(4:18)2024","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T10:30:09Z","timestamp":1733221809000},"source":"Crossref","is-referenced-by-count":1,"title":["Fine-grained Meta-Theorems for Vertex Integrity"],"prefix":"10.46298","volume":"Volume 20, Issue 4","author":[{"given":"Michael","family":"Lampis","sequence":"first","affiliation":[]},{"given":"Valia","family":"Mitsou","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2024,12,3]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/14874\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/14874\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T10:30:10Z","timestamp":1733221810000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,3]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-20(4:18)2024","relation":{"has-preprint":[{"id-type":"arxiv","id":"2109.10333v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2109.10333v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2109.10333v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2109.10333","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2109.10333","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,3]]},"article-number":"9398"}}