Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bannach, Max; Tantau, Till http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URL:

;

On the Descriptive Complexity of Color Coding

pdf-format:


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
Seminar: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue date: 2019
Date of publication: 2019


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI