Talks and Poster Presentations (with Proceedings-Entry):
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-13; in: "Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)",
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.