Linear kernelizations for restricted 3-Hitting Set problems
In this paper, we study the 3-HITTING SET problem, also called the VERTEX COVER problem on 3-uniform hypergraphs. We provide linear kernelizations for this problem and its dual problem in three types of 3-uniform hypergraphs. Moreover, we obtain lower bounds on the kernel size for them by the parametric duality technique. (C) 2009 Elsevier B.V. All rights reserved.
kernelization 3-hitting set problem computational complexity