3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size

We study upper and lower bounds on the vertex-kernel size for the 3-hitting set problem on hypergraphs of degree at most 3, denoted 3-3-hs. We first show that, unless P = NP, 3-3-hs on 3-uniform hypergraphs does not have a vertex-kernel of size at most 35k/19 > 1.8421k. We then give a 4k - k(0.2692) vertex-kernel for 3-3-hs that is computable in time O(k(2)). We do not assume that the hypergraph is 3-uniform for the vertex-kernel upper bound results. This result improves the upper bound of 4k on the vertex-kernel size for 3-3-hs, implied by the results of Wahlstrom.