Dynamic Kernels for Hitting Sets and Set Packing

Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau


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.
Original languageEnglish
PublisherComputational Complexity Foundation (CCF)
Number of pages24
Publication statusPublished - 31.10.2019

DFG Research Classification Scheme

  • 409-01 Theoretical Computer Science


Dive into the research topics of 'Dynamic Kernels for Hitting Sets and Set Packing'. Together they form a unique fingerprint.

Cite this