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.