3-hitting SET on Bounded Degree Hypergraphs: Upper and Lower Bounds on the Kernel Size

摘要

We study upper and lower bounds on the 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 kernel of size at most 35k/19 > 1.8421k. We then give a 4k - k~(0.2692) kernel for 3-3-HS that is computable in time O(k~(1.2692)). This result improves the upper bound of Ak on the kernel size for 3-3-HS, given by Wahlstrom. We also show that the upper bound results on the kernel size for 3-3-HS can be generalized to the 3-HS problem on hypergraphs of bounded degree A, for any integer-constant Δ > 3.