{"ID":2845797,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03461","arxiv_id":"2511.03461","title":"Dynamic Meta-Kernelization","abstract":"Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-hard graph problems on sparse graph classes. In this paper, we lift these results to the dynamic setting. As the canonical example, Alber, Fellows, and Niedermeier [J. ACM 2004] gave a linear kernel for dominating set on planar graphs. We provide the following dynamic version of their kernel: Our data structure is initialized with an $n$-vertex planar graph $G$ in $O(n \\log n)$ amortized time, and, at initialization, outputs a planar graph $K$ with $\\mathrm{OPT}(K) = \\mathrm{OPT}(G)$ and $|K| = O(\\mathrm{OPT}(G))$, where $\\mathrm{OPT}(\\cdot)$ denotes the size of a minimum dominating set. The graph $G$ can be updated by insertions and deletions of edges and isolated vertices in $O(\\log n)$ amortized time per update, under the promise that it remains planar. After each update to $G$, the data structure outputs $O(1)$ updates to $K$, maintaining $\\mathrm{OPT}(K) = \\mathrm{OPT}(G)$, $|K| = O(\\mathrm{OPT}(G))$, and planarity of $K$. Furthermore, we obtain similar dynamic kernelization algorithms for all problems satisfying certain conditions on (topological-)minor-free graph classes. Besides kernelization, this directly implies new dynamic constant-approximation algorithms and improvements to dynamic FPT algorithms for such problems. Our main technical contribution is a dynamic data structure for maintaining an approximately optimal protrusion decomposition of a dynamic topological-minor-free graph. Protrusion decompositions were introduced by Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, and Thilikos [J. ACM 2016], and have since developed into a part of the core toolbox in kernelization and parameterized algorithms.","short_abstract":"Kernelization studies polynomial-time preprocessing algorithms. Over the last 20 years, the most celebrated positive results of the field have been linear kernels for classical NP-hard graph problems on sparse graph classes. In this paper, we lift these results to the dynamic setting. As the canonical example, Alber, F...","url_abs":"https://arxiv.org/abs/2511.03461","url_pdf":"https://arxiv.org/pdf/2511.03461v1","authors":"[\"Christian Bertram\",\"Deborah Haun\",\"Mads Vestergaard Jensen\",\"Tuukka Korhonen\"]","published":"2025-11-05T13:34:44Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}