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 log 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(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 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.