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

14 Citations (Scopus)

Abstract

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
Pages41-53
Number of pages13
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event8th International Symposium on Parameterized and Exact Computation (IPEC 2013) - Sophia Antipolis, France
Duration: 4 Sep 20136 Sep 2013
Conference number: 8

Publication series

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

Conference

Conference8th International Symposium on Parameterized and Exact Computation (IPEC 2013)
Abbreviated titleIPEC 2013
CountryFrance
CitySophia Antipolis
Period4/09/136/09/13
Other8th International Symposium on Parameterized and Exact Computation

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

Cite this