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].

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