zbMATH — the first resource for mathematics

Kernelization algorithms for \(d\)-hitting set problems. (English) Zbl 1209.68610
Dehne, Frank (ed.) et al., Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15–17, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73948-7/pbk). Lecture Notes in Computer Science 4619, 434-445 (2007).
Summary: A kernelization algorithm for the 3-Hitting-Set problem is presented along with a general kernelization for \(d\)-Hitting-Set problems. For 3-Hitting-Set, a quadratic kernel is obtained by exploring properties of yes instances and employing what is known as crown reduction. Any 3-Hitting-Set instance is reduced into an equivalent instance that contains at most \(5k ^{2} + k\) elements (or vertices). This kernelization is an improvement over previously known methods that guarantee cubic-size kernels. Our method is used also to obtain a quadratic kernel for the Triangle Vertex Deletion problem. For a constant \(d \geq 3\), a kernelization of \(d\)-Hitting-Set is achieved by a generalization of the 3-Hitting-Set method, and guarantees a kernel whose order does not exceed \((2d - 1)k ^{d - 1} + k\).
For the entire collection see [Zbl 1123.68006].

68W05 Nonnumerical algorithms
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI