J. Chen, W. Czerwinski, Y. Disser, A. Feldmann, D. Hermelin, W. Nadara, M. Pilipczuk, M. Pilipczuk, M. Sorge, B. Wróblewski, A. Zych-Pawlewicz:

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

Talk: ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, Virginia, U.S.; 2021-01-10 - 2021-01-13; in: "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)", Siam, (2021), 796 - 809.

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 optimumheight

elimination forest. The data structure achieves

worst-case update time 2O(d2), 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 Dvorá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 dO(d).

As applications, we design new fully dynamic

parameterized data structures for detecting long paths

and cycles in general graphs. More precisely, for a fixed

parameter k and a dynamic graph G, modified over time by edge insertions and deletions, our data structures

maintain answers to the following queries:

. Does G contain a simple path on k vertices?

. Does G contain a simple cycle on at least k vertices?

In the first case, the data structure achieves amortized

update time 2O(k2). In the second case, the amortized

update time is 2O(k4) + O(k log n). In both cases we

assume access to a dictionary on the edges of G.

http://dx.doi.org/10.1137/1.9781611976465.50

https://publik.tuwien.ac.at/files/publik_300311.pdf

Created from the Publication Database of the Vienna University of Technology.