We present a data structure that for a dynamic graph G , which is updated by edge insertions and removals, maintains the answer to the query whether G contains a simple path on k vertices with amortized update time 2^{ {\cal O ( k ^2)}, assuming access to a dictionary on the edges of G. Underlying this result lies a data structure that maintains an optimum-depth elimination forest in a dynamic graphof treedepth at most d with update time 2^{O(d^2) . This improves a result of Dvor\'ak et al. [ESA 2014], who for the same problem achieved update time f(d) for a non-elementary function f(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^{{\cal O}(k^2)}. In the second case, the amortized update time is 2^{{\cal O}(k^4)} + }{\cal   .
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^{ {\cal 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 Dvor\'ak 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^{{\cal 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^{{\cal O}(k^2)}. In the second case, the amortized update time is 2^{{\cal O}(k^4)} + }{\cal O (k \log n). In both cases we assume access to a dictionary on the edges of G .
R
for
in
R
G
of treedepth at most d
R
updated
modified over time
R
removals, maintains the answer to the query whether G contains a simple path on k vertices with amortized
deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case
R
k
d
R
assuming access to a dictionary on the edges of G. Underlying this result lies a data structure that maintains an optimum-depth elimination forest in a dynamic graphof treedepth at most d with 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
R
a
some
R
function f
(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^{{\cal O
A
O
A
(k \log n). In both cases we assume access to a dictionary on the edges of G