Computing Hitting Set Kernels By AC0-Circuits.

Given a hypergraphH= (V,E), what is the smallest subsetX⊆Vsuch thate∩X6=∅holds for alle∈E? This problem, known as thehitting set problem,is a basic problem inparameterized complexity theory. There are well-known kernelization algorithms for it, whichget a hypergraphHand a numberkas input and output a hypergraphH′such that (1)Hhasa hitting set of sizekif, and only if,H′has such a hitting set and (2) the size ofH′dependsonly onkand on the maximum cardinalitydof edges inH. The algorithms run in polynomialtime, but are highly sequential. Recently, it has been shown that one of them can be parallelizedto a certain degree: one can compute hitting set kernels in parallel timeO(d)– but it wasconjectured that this is the best parallel algorithm possible. We refute this conjecture and showhow hitting set kernels can be computed inconstantparallel time. For our proof, we introducea new, generalized notion of hypergraph sunflowers and show how iterated applications of thecolor coding technique can sometimes be collapsed into a single application.

2012 ACM Subject Classification:
Mathematics of computing→Hypergraphs, Theory of computation→Fixed parameter tractability, Theory of computation→Circuit complexity

Keywords and phrases:
Parallel Computation, Fixed-parameter Tractability, Kernelization

Digital Object Identifier (DOI):
10.4230/LIPIcs.STACS.2018.9

Related Version:
Full proofs can be found in the full version of the paper [5],http://arxiv.org/abs/1801.00716.