2026-07-19T22:08:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20573 2024-08-23T05:50:28Z ddc:004 open_access

On the Descriptive Complexity of Vertex Deletion Problems Bannach, Max Chudigiewitsch, Florian Tantau, Till graph problems fixed-parameter tractability descriptive complexity vertex deletion Vertex deletion problems for graphs are studied intensely in classical and parameterized complexity theory. They ask whether we can delete at most k vertices from an input graph such that the resulting graph has a certain property. Regarding k as the parameter, a dichotomy was recently shown based on the number of quantifier alternations of first-order formulas that describe the property. In this paper, we refine this classification by moving from quantifier alternations to individual quantifier patterns and from a dichotomy to a trichotomy, resulting in a complete classification of the complexity of vertex deletion problems based on their quantifier pattern. The more fine-grained approach uncovers new tractable fragments, which we show to not only lie in FPT, but even in parameterized constant-depth circuit complexity classes. On the other hand, we show that vertex deletion becomes intractable already for just one quantifier per alternation, that is, there is a formula of the form ∀ x∃ y∀ z (ψ), with ψ quantifier-free, for which the vertex deletion problem is W[1]-hard. The fine-grained analysis also allows us to uncover differences in the complexity landscape when we consider different kinds of graphs and more general structures: While basic graphs (undirected graphs without self-loops), undirected graphs, and directed graphs each have a different frontier of tractability, the frontier for arbitrary logical structures coincides with that of directed graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Bannach and Florian Chudigiewitsch and Till Tantau 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.17 urn:nbn:de:0030-drops-205733 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode