Dynamic treewidth

Abstract

We present a data structure that for a dynamic graph $G$ that is updated by edge insertions and deletions, maintains a tree decomposition of $G$ of width at most $6k+5$ under the promise that the treewidth of $G$ never grows above $k$. The amortized update time is ${\mathcal{O}}_k(2^{\sqrt{\log n}\log \log n})$, where $n$ is the vertex count of $G$ and the ${\mathcal{O}}_k(\cdot )$ notation hides factors depending on $k$. In addition, we also obtain the dynamic variant of Courcelle's Theorem: for any fixed property $\phi$ expressible in the ${\mathsf{CMSO}}_2$ logic, the data structure can maintain whether $G$ satisfies $\phi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

80 pages, 2 figures