The fine details of fast dynamic programming over tree decompositions

Hans L. Bodlaender, P.S. Bonsma, Daniel Lokshtanov

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

13 Citations (Scopus)
5 Downloads (Pure)

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(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.
Original languageEnglish
Title of host publicationProceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)
EditorsG. Gutin, S. Szeider
Place of PublicationBerlin
PublisherSpringer
Pages41-53
Number of pages13
ISBN (Print)978-3-319-03897-1
DOIs
Publication statusPublished - Sep 2013
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
PublisherSpringer Verlag
Volume8246
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

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

Keywords

  • EWI-23839
  • tree decomposition
  • Graph algorithms
  • IR-88274
  • Treewidth
  • METIS-300088
  • Dynamic Programming

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

    Bodlaender, H. L., Bonsma, P. S., & Lokshtanov, D. (2013). The fine details of fast dynamic programming over tree decompositions. In G. Gutin, & S. Szeider (Eds.), Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013) (pp. 41-53). (Lecture Notes in Computer Science; Vol. 8246). Berlin: Springer. https://doi.org/10.1007/978-3-319-03898-8_5