Dynamic treewidth

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 $6 k+5$ under the promise that the treewidth of G never grows above k. The amortized update time is $\mathcal{O}_{k}\left(2^{\sqrt{\log n} \log \log n}\right)$, 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 $\varphi$ expressible in the CMSO 2 logic, the data structure can maintain whether G satisfies $\varphi$ within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

Authors

• Tuukka Korhonen
• Konrad Majewski
• Wojciech Nadara
• Michal Pilipczuk
• Marek Sokolowski 0001

Keywords

• Computer science
• Heuristic algorithms
• Automata
• Data structures
• Approximation algorithms
• Dynamic programming
• Complexity theory
• Data Structure
• Update Time
• Joining Tree
• Dynamic Graph
• Running Time
• Estimation Algorithm
• Algorithm Design
• Subtree
• Dynamic Setting
• Dynamic Problem
• Binary Tree
• Tree Depth
• Time Graph
• Dynamic Procedure
• High-level Description
• Planar Graphs
• Induced Subgraph
• Worst-case Time
• Subset Of Vertices
• Existence Of Edges
• Graph Parameters
• Optimum Width
• Polylogarithmic
• Structural Dynamics
• Scheme For Problem
• treewidth
• parameterized algorithms
• dynamic algorithms
• graph algorithms