2026-08-08T04:31:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10250 2024-03-06T10:45:37Z ddc:004 open_access

On the Descriptive Complexity of Color Coding Bannach, Max Tantau, Till color coding descriptive complexity fixed-parameter tractability quantifier elimination para-AC^0 Color coding is an algorithmic technique used in parameterized complexity theory to detect "small" structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing - purely in terms of the syntactic structure of describing formulas - when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in fpt just because of the way they are commonly described using logical formulas. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Bannach and Till Tantau 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.11 urn:nbn:de:0030-drops-102509 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.11 eng https://creativecommons.org/licenses/by/3.0/legalcode