2022

• 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.

2021

• Max Bannach, Zacharias Heinrich, Till Tantau, Rüdiger Reischuk:
  Dynamic Kernels for Hitting Sets and Set Packing.
  In Proceedings of the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Band 214 von LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  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 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.

2019

• Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
  Dynamic Kernels for Hitting Sets and Set Packing.
  Technischer Bericht , Electronic Colloquium on Computational Complexity, 2019.
  Website anzeigen | Zusammenfassung anzeigen
  
  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 \emph{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$.
• Zacharias Heinrich, Rüdiger Reischuk:
  Improved Dynamic Kernels for Hitting-Set.
  In 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, S. 69-72. Inproceedings, 2019.
  PDF anzeigen