The 3- problem is also called the problem on 3-uniform hypergraphs. In this paper, we address kernelizations of the 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.
Given a collection C of subsets of size three of a finite set S and a positive integer k, the 3-Hitting Set problem is to determine a subset S' ⊆ S with |S'| ≤ k, so that S' contains at least one element from each subset in C. The problem is NP-complete, and is motivated, for example, by applications in computational biology. Improving previous work, we give an O(2.270k + n) time algorithm for 3-Hitting Set, which is efficient for small values of k, a typical occurrence in some applications. For d-Hitting Set we present an O(ck + n) time algorithm with c = d - 1 + O(d-1). Classes of machines using very limited amounts of nondeterminism are studied. The @math question is related to questions about classes lying within P. Complete sets for these classes are given.