2025/06/30 by Liu, Yuxi, Xiao, Mingyu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2506.24114
The d-Hitting Set problem is a fundamental problem in parameterized complexity, which asks whether a given hypergraph contains a vertex subset S of size at most k that intersects every hyperedge (i.e., S ∩ e ≠ ∅ for each hyperedge e). The best known kernel for this problem, established by Abu-Khzam [1], has (2d - 1)kd - 1 + k vertices. This result has been very widely used in the literature as many problems can be modeled as a special d-Hitting Set problem. In this work, we present a refinement to this result by employing linear programming techniques to construct crown decompositions in hypergraphs. This approach yields a slight but notable improvement, reducing the size to (2d - 2)kd - 1 + k vertices.