Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

Abstrakt

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).

Klíčová slova

• Fully dynamic
• elimination forests