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

6 Citations (Scopus)
4 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

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume8246
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dynamic programming
Decomposition
Computational complexity
Polynomials
Testing

Keywords

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

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
Bodlaender, Hans L. ; Bonsma, P.S. ; Lokshtanov, Daniel. / The fine details of fast dynamic programming over tree decompositions. Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013). editor / G. Gutin ; S. Szeider. Berlin : Springer, 2013. pp. 41-53 (Lecture Notes in Computer Science).
@inproceedings{831e636f356348bab4793ededed568c9,
title = "The fine details of fast dynamic programming over tree decompositions",
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.",
keywords = "EWI-23839, tree decomposition, Graph algorithms, IR-88274, Treewidth, METIS-300088, Dynamic Programming",
author = "Bodlaender, {Hans L.} and P.S. Bonsma and Daniel Lokshtanov",
year = "2013",
month = "9",
doi = "10.1007/978-3-319-03898-8_5",
language = "English",
isbn = "978-3-319-03897-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "41--53",
editor = "G. Gutin and S. Szeider",
booktitle = "Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)",

}

Bodlaender, HL, Bonsma, PS & 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). Lecture Notes in Computer Science, vol. 8246, Springer, Berlin, pp. 41-53. https://doi.org/10.1007/978-3-319-03898-8_5

The fine details of fast dynamic programming over tree decompositions. / Bodlaender, Hans L.; Bonsma, P.S.; Lokshtanov, Daniel.

Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013). ed. / G. Gutin; S. Szeider. Berlin : Springer, 2013. p. 41-53 (Lecture Notes in Computer Science; Vol. 8246).

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

TY - GEN

T1 - The fine details of fast dynamic programming over tree decompositions

AU - Bodlaender, Hans L.

AU - Bonsma, P.S.

AU - Lokshtanov, Daniel

PY - 2013/9

Y1 - 2013/9

N2 - 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.

AB - 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.

KW - EWI-23839

KW - tree decomposition

KW - Graph algorithms

KW - IR-88274

KW - Treewidth

KW - METIS-300088

KW - Dynamic Programming

U2 - 10.1007/978-3-319-03898-8_5

DO - 10.1007/978-3-319-03898-8_5

M3 - Conference contribution

SN - 978-3-319-03897-1

T3 - Lecture Notes in Computer Science

SP - 41

EP - 53

BT - Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)

A2 - Gutin, G.

A2 - Szeider, S.

PB - Springer

CY - Berlin

ER -

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