We present a dynamic data structure that maintains a tree decomposition of width at most 9k+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^{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 $O_k(\log n)$ amortized update time; the $O_k(⋅)$ 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^{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.
This talk is based on arXiv:2504.02790.
On November 25, 2021, Tuukka Korhonen from the University of Bergen gave an online talk on a faster FPT-approximation algorithm for rank-width at the Virtual Discrete Math Colloquium. The title of his talk was “Fast FPT-Approximation of Branchwidth“.
Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework.
- An algorithm that for a given n-vertex graph G and integer k in time $2^{2^{O(k)}} n^2$ either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than $k$. It also yields a $(2^{2k+1}−1)$-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to $f(k) n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.
- An algorithm that for a given n-vertex graph G and integer k in time $2^{O(k)} n$ either constructs a branch decomposition of G of width at most $2k$ or concludes that the branchwidth of G is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].
This is joint work with Fedor Fomin.
