## René van Bevern.
Towards optimal and expressive kernelization for *d*-hitting set.
*Algorithmica*, 70(1):129–147, 2014.
COCOON'12 special issue.

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 (whose
cardinality is bounded from above by a constant 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) and
provide experimental results that show the practical
applicability of our algorithm. Finally, 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 |
source code |
http ]
Back

*This file was generated by
bibtex2html 1.98.*