2008/09/01 by Xuan Cai, Cai, Xuan
Computer Science · #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.0809.0257
12 pages
arxiv created 2008/09/20 · arxiv updated 2009/12/01
The 3-Hitting Set problem is also called the Vertex Cover problem on 3-uniform hypergraphs. In this paper, we address kernelizations of the Vertex Cover problem on 3-uniform hypergraphs. We show that this problem admits a linear kernel in three classes of 3-uniform hypergraphs. We also obtain lower and upper bounds on the kernel size for them by the parametric duality.