Towards optimal and expressive kernelization for \(d\)-hitting set. (English) Zbl 1364.68237

van Bevern, René

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)