Speeding up dynamic programming with representative sets

S. Fafianie, H.L. Bodlaender, J. Nederlof

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

5 Citations (Scopus)


Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al. [5], it was shown that for many connectivity problems, there exist algorithms that use time, linear in the number of vertices, and single exponential in the width of the tree decomposition that is used. The central idea is that it suffices to compute representative sets, and these can be computed efficiently with help of Gaussian elimination. In this paper, we give an experimental evaluation of this technique for the Steiner Tree problem. A comparison of the classic dynamic programming algorithm and the improved dynamic programming algorithm that employs the table reduction shows that the new approach gives significant improvements on the running time of the algorithm and the size of the tables computed by the dynamic programming algorithm, and thus that the rank based approach from Bodlaender et al. [5] does not only give significant theoretical improvements but also is a viable approach in a practical setting, and showcases the potential of exploiting the idea of representative sets for speeding up dynamic programming algorithms. Keywords: Experimental evaluation; Algorithmic engineering; Steiner tree; Treewidth; Dynamic programming; Exact algorithms
Original languageEnglish
Title of host publicationParameterized and Exact Computation (8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers)
EditorsG. Gutin, S. Szeider
Place of PublicationBerlin
ISBN (Print)978-3-319-03897-1
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)0302-9743


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 'Speeding up dynamic programming with representative sets'. Together they form a unique fingerprint.

Cite this