Jiehua Chen

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time $2^{O(d^2)}$, which matches the best known parameter dependency in the running time of a static FPT algorithm for computing the treedepth of a graph. This improves a result of Dvořá k et al. [ESA 2014], who for the same problem achieved update time $f(d)$ for some non-elementary (i.e. tower-exponential) function $f$. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth $d$ from doubly-exponential in $d$ to $d^{O(d)}$.

As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs.

====================================

The paper can be found at SODA21.