The fine details of fast dynamic programming over tree decompositions

H.L. Bodlaender, P. Bonsma, D. Lokshtanov

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

19 Citations (Scopus)


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(qk+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(2k n) algorithms for Max Independent Set and Max Cut, and a O(qk+1 n) algorithm for q-Colorability. The table building techniques we develop are also useful for many other problems.

Original languageEnglish
Title of host publicationParameterized and Exact Computation - 8th International Symposium, IPEC 2013, Revised Selected Papers
Number of pages13
Publication statusPublished - 2013
Externally publishedYes
Event8th International Symposium on Parameterized and Exact Computation, IPEC 2013 - Sophia Antipolis, France
Duration: 4 Sept 20136 Sept 2013
Conference number: 8

Publication series

NameLecture Notes in Computer Science
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference8th International Symposium on Parameterized and Exact Computation, IPEC 2013
Abbreviated titleIPEC 2013
CitySophia Antipolis
Other8th International Symposium on Parameterized and Exact Computation


Dive into the research topics of 'The fine details of fast dynamic programming over tree decompositions'. Together they form a unique fingerprint.

Cite this