Dynamic treewidth
| Autor: | Korhonen, Tuukka, Majewski, Konrad, Nadara, Wojciech, Pilipczuk, Michał, Sokołowski, Marek |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 ${\cal O}_k(2^{\sqrt{\log n}\log\log n})$, where $n$ is the vertex count of $G$ and the ${\cal 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 $\mathsf{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]. Comment: 80 pages, 2 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|