Dynamic Meta-Kernelization

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 n) amortized time, and, at initialization, outputs a planar graph K with OPT (K) = OPT (G) and |K| = O (OPT (G) ), where OPT () 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 (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 OPT (K) = OPT (G), |K| = O (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.