In pursuit of a dynamic tree decomposition

J. Iacono and B. Vogtenhuber

Abstract:

Treewidth is a measure of a graph's similarity to a tree. Since its introduction [#!DBLP:journals_jal_RobertsonS86!#], it has gained wide popularity as many problems can be solved much faster under the assumption of bounded treewidth. The definition of treewidth depends on the existence of a structure known as a tree decomposition, and many treewidth dependent algorithms begin by constructing this decomposition. One natural question is: can a tree decomposition of small width be maintained under dynamic changes in the graph?We examine a restricted class of graphs whereby the tree decomposition can be computed in linear time, and show that for such a class of graphs it can be maintained dynamically.

Reference: J. Iacono and B. Vogtenhuber. In pursuit of a dynamic tree decomposition. In Proceedings of the of the 21st Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3$\,$2018), pages 23-25, Manila, Philippines, 2018.