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.
BibTeX - Entry
@InProceedings{bannach_et_al:LIPIcs:2019:10250,
author = {Max Bannach and Till Tantau},
title = {{On the Descriptive Complexity of Color Coding}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {11:1--11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-100-9},
ISSN = {1868-8969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10250},
doi = {10.4230/LIPIcs.STACS.2019.11},
annote = {Keywords: color coding, descriptive complexity, fixed-parameter tractability, quantifier elimination, para-AC^0}
}
|
Keywords: |
|
color coding, descriptive complexity, fixed-parameter tractability, quantifier elimination, para-AC^0 |
|
Collection: |
|
36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
12.03.2019 |
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)