## René van Bevern.
Towards optimal and expressive kernelization for *d*-hitting set.
In *Proceedings of the 18th Annual International Computing and
Combinatorics Conference (COCOON'12), Sydney, Australia*, volume 7434 of *
Lecture Notes in Computer Science*, pages 121–132. Springer, 2012.
The final version of this article appeared in the COCOON'12 special
issue of Algorithmica.

A sunflower in a hypergraph is a set of hyperedges
pairwise intersecting in exactly the same vertex
set. Sunflowers are a useful tool in polynomial-time
data reduction for problems formalizable as d-Hitting
Set, the problem of covering all hyperedges (of
cardinality at most d) of a hypergraph by at most k
vertices. Additionally, in fault diagnosis, sunflowers
yield concise explanations for “highly defective
structures”. We provide a linear-time algorithm that,
by finding sunflowers, transforms an instance of
d-Hitting Set into an equivalent instance comprising
at most O(k^d) hyperedges and vertices. In terms of
parameterized complexity, we show a problem kernel
with asymptotically optimal size (unless
coNP ⊆ NP/poly). We show that the number of vertices
can be reduced to O(k^(d−1)) with additional
processing in O(k^(1.5d)) time—nontrivially combining
the sunflower technique with problem kernels due to
Abu-Khzam and Moser.

[ bib |
DOI |
slides |
journal version ]
Back

*This file was generated by
bibtex2html 1.98.*