Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
Dynamic Kernels for Hitting Sets and Set Packing.
Algorithmica, 84:3459–3488, 2022.
Website anzeigen | Zusammenfassung anzeigen
Computing small kernels for the hitting set problem is a well-studied computational
problem where we are given a hypergraph with n vertices and m hyperedges, each of
size d for some small constant d, and a parameter k. The task is to compute a new
hypergraph, called a kernel, whose size is polynomial with respect to the parameter k
and which has a size-k hitting set if, and only if, the original hypergraph has one.
State-of-the-art algorithms compute kernels of size k d (which is a polynomial as d is a
constant), and they do so in time m · 2d poly(d) for a small polynomial poly(d) (which
is linear in the hypergraph size for d fixed). We generalize this task to the dynamic
setting where hyperedges may continuously be added or deleted and one constantly
has to keep track of a size-k d kernel. This paper presents a deterministic solution with
worst-case time 3d poly(d) for updating the kernel upon inserts and time 5d poly(d)
for updates upon deletions. These bounds nearly match the time 2d poly(d) needed by
the best static algorithm per hyperedge. Let us stress that for constant d our algorithm
maintains a hitting set kernel with constant, deterministic, worst-case update time that
is independent of n, m, and the parameter k. As a consequence, we also get a deter-
ministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs
with update times O(1) and query times O(c k ) where c = d ? 1 + O(1/d) equals
the best base known for the static setting.
