The fine details of fast dynamic programming over tree decompositions

We study implementation details for dynamic programming over tree decompositions. Firstly, a fact that is overlooked in many papers and books on this subject is that it is not clear how to test adjacency between two vertices in time bounded by a function of $k$, where $k$ is the width of the given tree decomposition. This is necessary to obtain linear time dynamic programming algorithms. We address this by giving a simple $O(kn)$ time and space preprocessing procedure that enables adjacency testing in time $O(k)$, where $n$ is the number of vertices of the graph. Secondly, we show that a large class of NP-hard problems can be solved in time $O(q^{k+1} n)$, where $q^{k+1}$ is the natural size of the dynamic programming tables. The key improvement is that we avoid a polynomial factor in $k$. This holds for all problems that can be formulated as a Min Weight Homomorphism problem: given a (di)graph $G$ on $n$ vertices and a (di)graph $H$ on $q$ vertices, with integer vertex and edge weights, is there a homomorphism from $G$ to $H$ with total (vertex and edge image) weight at most $M$? This result implies e.g.\ $O(2^k n)$ algorithms for Max Independent Set and Max Cut, and a $O(q^{k+1} n)$ algorithm for $q$-Colorability. The table building techniques we develop are also useful for many other problems.