Parallel Multivariate Meta-Theorems

Max Bannach, Till Tantau


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 \emph{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.

Original languageEnglish
Title of host publication11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
EditorsJiong Guo , Danny Hermelin
Number of pages14
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date01.02.2017
Pages4 - 17
ISBN (Print)978-3-95977-023-1
Publication statusPublished - 01.02.2017
Event11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
- Aarhus, Denmark
Duration: 24.08.201626.08.2016


Dive into the research topics of 'Parallel Multivariate Meta-Theorems'. Together they form a unique fingerprint.

Cite this