2026-07-25T13:22:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15390 2024-03-06T10:55:38Z ddc:004 open_access

Dynamic Kernels for Hitting Sets and Set Packing Bannach, Max Heinrich, Zacharias Reischuk, Rüdiger Tantau, Till Kernelization Dynamic Algorithms Hitting Set Set Packings 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 kernel size as d is a constant), and they do so in time m⋅ 2^d poly(d) for a small polynomial poly(d) (which is a linear runtime as d is again a constant). 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 hitting set kernel in memory (including moments when no size-k hitting set exists). This paper presents a deterministic solution with worst-case time 3^d poly(d) for updating the kernel upon hyperedge inserts and time 5^d poly(d) for updates upon deletions. These bounds nearly match the time 2^d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a dynamic 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 deterministic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max Bannach and Zacharias Heinrich and Rüdiger Reischuk and Till Tantau 2021 Is Part Of LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2021.7 urn:nbn:de:0030-drops-153900 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode