BARC Talk by Tuukka Korhonen: Dynamic treewidth

Abstract:

The treewidth of a graph, defined as the minimum width of a tree decomposition of the graph, informally speaking characterizes how tree-like the graph is. Treewidth plays an important role in many areas of computer science and graph theory, in particular generalizing results on trees to graphs of small treewidth.

We present a data structure that for a dynamic n-vertex 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 subpolynomial in n for fixed k, in particular, f(k) 2^(sqrt(log n) log log n) for some function f(k). Additionally, our data structure can maintain any finite-state dynamic programming scheme on the tree decomposition within the same running time, maintaining for example the chromatic number, the size of the maximum independent set, and the exact treewidth of G. This is the first fully dynamic algorithm for maintaining tree decompositions of width bounded by a function of k.

Based on joint work with Konrad Majewski, Wojciech Nadara, Michał Pilipczuk, and Marek Sokołowski.