Dynamic Treewidth in Logarithmic Time

We present a dynamic data structure that maintains a tree decomposition of width at most $9 k+8$ of a dynamic graph with treewidth at most k, which is updated by edge insertions and deletions. The amortized update time of our data structure is $2^{\mathcal{O}(k)} \log n$, where n is the number of vertices. The data structure also supports maintaining any “dynamic programming scheme” on the tree decomposition, providing, for example, a dynamic version of Courcelle’s theorem with ${\mathcal{O}}_{k}(\log n)$ amortized update time; the ${\mathcal{O}}_{k}(\cdot)$ notation hides factors that depend on k. This improves upon a result of Korhonen, Majewski, Nadara, Pilipczuk, and Sokołowski [FOCS 2023], who gave a similar data structure but with amortized update time $2^{k^{\mathcal{O}(1)}} n^{o(1)}$. Furthermore, our data structure is arguably simpler. Our main novel idea is to maintain a tree decomposition that is “downwards well-linked”, which allows us to implement local rotations and analysis similar to those for splay trees.