TR19-146 Authors: Max Bannach, Zacharias Heinrich, RĂ¼diger Reischuk, Till Tantau

Publication: 31st October 2019 15:46

Downloads: 74

Keywords:

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(k^d)$ in time $O(2^d m)$. 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^*(3^d)$ for updating the kernel upon hyperedge inserts and

time~$O^*(5^d)$ for updates upon deletions -- thus nearly matching

the time $O^*(2^d)$ 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 $\sum_{i=0}^d k^i$

rather than the typical size $d!\cdot k^d$ 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

$\sum_{i=0}^d d^i(k-1)^i$.