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.2018.13
URN: urn:nbn:de:0030-drops-102148
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10214/
Go to the corresponding LIPIcs Volume Portal

Bannach, Max ; Tantau, Till

Computing Kernels in Parallel: Lower and Upper Bounds

pdf-format:
LIPIcs-IPEC-2018-13.pdf (0.5 MB)

Abstract

Parallel fixed-parameter tractability studies how parameterized problems can be solved in parallel. A surprisingly large number of parameterized problems admit a high level of parallelization, but this does not mean that we can also efficiently compute small problem kernels in parallel: known kernelization algorithms are typically highly sequential. In the present paper, we establish a number of upper and lower bounds concerning the sizes of kernels that can be computed in parallel. An intriguing finding is that there are complex trade-offs between kernel size and the depth of the circuits needed to compute them: For the vertex cover problem, an exponential kernel can be computed by AC^0-circuits, a quadratic kernel by TC^0-circuits, and a linear kernel by randomized NC-circuits with derandomization being possible only if it is also possible for the matching problem. Other natural problems for which similar (but quantitatively different) effects can be observed include tree decomposition problems parameterized by the vertex cover number, the undirected feedback vertex set problem, the matching problem, or the point line cover problem. We also present natural problems for which computing kernels is inherently sequential.

BibTeX - Entry

@InProceedings{bannach_et_al:LIPIcs:2019:10214,
  author =	{Max Bannach and Till Tantau},
  title =	{{Computing Kernels in Parallel: Lower and Upper Bounds}},
  booktitle =	{13th International Symposium on Parameterized and Exact  Computation (IPEC 2018)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Christophe Paul and Michal Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10214},
  URN =		{urn:nbn:de:0030-drops-102148},
  doi =		{10.4230/LIPIcs.IPEC.2018.13},
  annote =	{Keywords: parallel computation, fixed-parameter tractability, kernelization}
}

Keywords: parallel computation, fixed-parameter tractability, kernelization
Collection: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Issue Date: 2019
Date of publication: 05.02.2019

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