Before revision: 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) .
After revision: We present a data structure that for a dynamic graph of treedepth at most d , 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) .