Computational Techniques for Join Operations for Dynamic Programming Algorithms on Tree Decompositions

Abstract

Tree decompositions can be traversed with a dynamic programming algorithm in order to compute exact answers to various graph problems. A particular operation called a join operation is performed in these algorithms, and commonly this operation forms the bottleneck. In this master thesis, I will present a number of different results pertaining to these join operations. First, we will see that every 2×2 join operation can be computed in O*(2k), where k represents treewidth. We will see that two s×s join operations, named the Fourier- and Möbius-Transform-based join operations, can be computed in O*(sk). We will introduce a new technique called filtering that computes join operations by computing a different but related join operation and doing only polynomially extra work. We will use this technique to prove a new result relating to an extension of Disjoint Set Sum.