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.STACS.2018.9
URN: urn:nbn:de:0030-drops-84998
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8499/
Go to the corresponding LIPIcs Volume Portal

Bannach, Max ; Tantau, Till

Computing Hitting Set Kernels By AC^0-Circuits

pdf-format:
LIPIcs-STACS-2018-9.pdf (0.6 MB)

Abstract

Given a hypergraph H = (V,E), what is the smallest subset X of V such that e and X are not disjoint for all e in E? This problem, known as the hitting set problem, is a basic problem in parameterized complexity theory. There are well-known kernelization algorithms for it, which get a hypergraph H and a number k as input and output a hypergraph H' such that (1) H has a hitting set of size k if, and only if, H' has such a hitting set and (2) the size of H' depends only on k and on the maximum cardinality d of edges in H. The algorithms run in polynomial time, but are highly sequential. Recently, it has been shown that one of them can be parallelized to a certain degree: one can compute hitting set kernels in parallel time O(d) - but it was conjectured that this is the best parallel algorithm possible. We refute this conjecture and show how hitting set kernels can be computed in constant parallel time. For our proof, we introduce a new, generalized notion of hypergraph sunflowers and show how iterated applications of the color coding technique can sometimes be collapsed into a single application.

BibTeX - Entry

@InProceedings{bannach_et_al:LIPIcs:2018:8499,
  author =	{Max Bannach and Till Tantau},
  title =	{{Computing Hitting Set Kernels By AC^0-Circuits}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8499},
  URN =		{urn:nbn:de:0030-drops-84998},
  doi =		{10.4230/LIPIcs.STACS.2018.9},
  annote =	{Keywords: parallel computation, fixed-parameter tractability, kernelization}
}

Keywords: parallel computation, fixed-parameter tractability, kernelization
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

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