License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2016.4
URN: urn:nbn:de:0030-drops-69227
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6922/
Go to the corresponding LIPIcs Volume Portal

Bannach, Max ; Tantau, Till

Parallel Multivariate Meta-Theorems

pdf-format:
LIPIcs-IPEC-2016-4.pdf (0.5 MB)

Abstract

Fixed-parameter tractability is based on the observation that many hard problems become tractable even on large inputs as long as certain input parameters are small. Originally, "tractable" just meant "solvable in polynomial time," but especially modern hardware raises the question of whether we can also achieve "solvable in polylogarithmic parallel time." A framework for this study of parallel fixed-parameter tractability is available and a number of isolated algorithmic results have been obtained in recent years, but one of the unifying core tools of classical FPT theory has been missing: algorithmic meta-theorems. We establish two such theorems by giving new upper bounds on the circuit depth necessary to solve the model checking problem for monadic second-order logic, once parameterized by the tree width and the formula (this is a parallel version of Courcelle's Theorem) and once by the tree depth and the formula. For our proofs we refine the analysis of earlier algorithms, especially of Bodlaender's, but also need to add new ideas, especially in the context where the parallel runtime is bounded by a function of the parameter and does not depend on the length of the input.

BibTeX - Entry

@InProceedings{bannach_et_al:LIPIcs:2017:6922,
  author =	{Max Bannach and Till Tantau},
  title =	{{Parallel Multivariate Meta-Theorems}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Jiong Guo and Danny Hermelin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6922},
  URN =		{urn:nbn:de:0030-drops-69227},
  doi =		{10.4230/LIPIcs.IPEC.2016.4},
  annote =	{Keywords: Parallel computation, FPT, meta-theorems, tree width, tree depth}
}

Keywords: Parallel computation, FPT, meta-theorems, tree width, tree depth
Collection: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Issue Date: 2017
Date of publication: 09.02.2017

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