# zbMATH — the first resource for mathematics

Towards optimal and expressive kernelization for $$d$$-hitting set. (English) Zbl 1364.68237
Gudmundsson, Joachim (ed.) et al., Computing and combinatorics. 18th annual international conference, COCOON 2012, Sydney, Australia, August 20–22, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32240-2/pbk). Lecture Notes in Computer Science 7434, 121-132 (2012).
Summary: 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 $$\text{coNP} \subseteq \text{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.
For the entire collection see [Zbl 1246.68037].

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 05C65 Hypergraphs 05C85 Graph algorithms (graph-theoretic aspects)
Full Text: