Fully dynamic approximation schemes on planar and apex-minor-free graphs

Abstract

The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings throughout the last 30 years. In this work we propose a dynamic variant of Baker's technique, where instead of finding an approximate solution in a given static graph, the task is to design a data structure for maintaining an approximate solution in a fully dynamic graph, that is, a graph that is changing over time by edge deletions and edge insertions. Specifically, we address the two most basic problems -- Maximum Weight Independent Set and Minimum Weight Dominating Set -- and we prove the following: for a fully dynamic $n$-vertex planar graph $G$, one can: * maintain a $(1-\epsilon )$-approximation of the maximum weight of an independent set in $G$ with amortized update time $f(\epsilon )\cdot n^{o(1)}$; and, * under the additional assumption that the maximum degree of the graph is bounded at all times by a constant, also maintain a $(1+\epsilon )$-approximation of the minimum weight of a dominating set in $G$ with amortized update time $f(\epsilon )\cdot n^{o(1)}$. In both cases, $f(\epsilon )$ is doubly-exponential in $\mathrm{poly}(1/\epsilon )$ and the data structure can be initialized in time $f(\epsilon )\cdot n^{1+o(1)}$. All our results in fact hold in the larger generality of any graph class that excludes a fixed apex-graph as a minor.

37 pages, accepted to SODA '24