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.