Dynamic Kernels for Hitting Sets and Set Packing

Computing kernels for the hitting set problem (the problem of finding a size-k set that intersects each hyperedge of a hypergraph) is a well-studied computational problem. For hypergraphs with m hyperedges, each of size at most d, the best algorithms can compute kernels of size O(kd) in time O(2dm). In this paper we generalize the task to the dynamic setting where hyperedges may be continuously added and deleted and we always have to keep track of a hitting set kernel (including moments when no size-k hitting set exists). We present a deterministic solution, based on a novel data structure, that needs worst-case time O∗(3d) for updating the kernel upon hyperedge inserts and time O∗(5d) for updates upon deletions – thus nearly matching the time O∗(2d) needed by the best static algorithm per hyperedge. As a novel technical feature, our approach does not use the standard replace- sunflowers-by-their-cores methodology, but introduces a generalized concept that is actually easier to compute and that allows us to achieve a kernel size of ﰆdi=0 ki rather than the typical size d! · kd resulting from the Sunflower Lemma. We also show that our approach extends to the dual problem of finding packings in hypergraphs (the problem of finding k pairwise disjoint hyperedges), albeit with a slightly larger kernel size of ﰆdi=0 di(k − 1)i.