A kernelization algorithm for d-Hitting Set
For a given parameterized problem, π, a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of π into an equivalent one whose size depends only on the input parameter(s). The resulting instance is called a problem kernel. In this paper, a kerne...
Saved in:
| Main Author: | |
|---|---|
| Format: | article |
| Published: |
2010
|
| Online Access: | http://hdl.handle.net/10725/2772 http://dx.doi.org/10.1016/j.jcss.2009.09.002 http://www.sciencedirect.com/science/article/pii/S0022000009000786 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | For a given parameterized problem, π, a kernelization algorithm is a polynomial-time pre-processing procedure that transforms an arbitrary instance of π into an equivalent one whose size depends only on the input parameter(s). The resulting instance is called a problem kernel. In this paper, a kernelization algorithm for the 3-Hitting Set problem is presented along with a general kernelization for d -Hitting Set. For 3-Hitting Set, an arbitrary instance is reduced into an equivalent one that contains at most 5k2+k elements. This kernelization is an improvement over previously known methods that guarantee cubic-order kernels. Our method is used also to obtain quadratic kernels for several other problems. For a constant d⩾3, a kernelization of d -Hitting Set is achieved by a non-trivial generalization of the 3-Hitting Set method, and guarantees a kernel whose order does not exceed (2d−1)kd−1+k. |
|---|