Abstract
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.
Original language | English |
---|---|
Title of host publication | 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
Editors | Rolf Niedermeier, Christophe Paul |
Number of pages | 16 |
Volume | 126 |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publication date | 01.03.2019 |
Pages | 11:1--11:16 |
Article number | 11 |
ISBN (Print) | 978-3-95977-100-9 |
DOIs | |
Publication status | Published - 01.03.2019 |
Event | 36th International Symposium on Theoretical Aspects of Computer Science - Berlin, Germany Duration: 13.03.2019 → 16.03.2019 Conference number: 153790 |
DFG Research Classification Scheme
- 4.43-01 Theoretical Computer Science