Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwinski, Yann Disser, Andreas Emil Feldmann, Danny Hermelin, Wojciech Nadara, Marcin Pilipczuk, Michal Pilipczuk, Manuel Sorge, Bartlomiej Wróblewski, Anna Zych-Pawlewicz
Abstract
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. 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 2 O(k 2 ) . In the second case, the amortized update time is 2 O(k 4 ) + O(k log n). In both cases we assume access to a dictionary on the edges of G.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Dynamic Treewidth in Logarithmic Time cites Dynamic treewidth
- Dynamic Treewidth in Logarithmic Time cites Dynamic Meta-Kernelization
- Dynamic Meta-Kernelization cites Dynamic Treewidth in Logarithmic Time
- Dynamic Meta-Kernelization cites Dynamic treewidth
Cited by top-tier papers4
- Dynamic Treewidth in Logarithmic TimeTuukka KorhonenFOCS 2025 · 4 citations
- Dynamic treewidthTuukka Korhonen, Konrad Majewski, Wojciech Nadara, Michal Pilipczuk et al.FOCS 2023 · 2 citations
- Dynamic Meta-KernelizationChristian Bertram, Deborah Haun, Mads Vestergaard Jensen, Tuukka KorhonenSTOC 2026 · 2 citations
- Meta-theorems for Parameterized Streaming Algorithms‡Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, M. S. Ramanujan et al.SODA 2024 · 1 citation
Builds on2
Related papers
- Fully Dynamic Exact Edge Connectivity in Sublinear TimeGramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak et al.SODA 2023 · 3 citations
- Deterministic Incremental APSP with Polylogarithmic Update Time and StretchSebastian Forster, Yasamin Nazari, Maximilian Probst GutenbergSTOC 2023 · 2 citations
- Subquadratic dynamic path reporting in directed graphs against an adaptive adversaryAdam Karczmarz, Anish Mukherjee, Piotr SankowskiSTOC 2022 · 5 citations
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive AdversaryMaximilian Probst Gutenberg, Christian Wulff-NilsenSODA 2020 · 19 citations
- Weighted k-Path and Other Problems in Almost O*(2k) Deterministic Time via Dynamic Representative Sets†Jesper NederlofFOCS 2025 · 4 citations
