### 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 language | English |
---|---|

Title of host publication | Proceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC 2013) |

Editors | G. Gutin, S. Szeider |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 41-53 |

Number of pages | 13 |

ISBN (Print) | 978-3-319-03897-1 |

DOIs | |

Publication status | Published - Sep 2013 |

Event | 8th International Symposium on Parameterized and Exact Computation, IPEC 2013 - Sophia Antipolis, France Duration: 4 Sep 2013 → 6 Sep 2013 Conference number: 8 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Volume | 8246 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 8th International Symposium on Parameterized and Exact Computation, IPEC 2013 |
---|---|

Abbreviated title | IPEC 2013 |

Country | France |

City | Sophia Antipolis |

Period | 4/09/13 → 6/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