Speeding up dynamic programming with representative sets

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

Abstract

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
PublisherSpringer
Pages321-334
ISBN (Print)978-3-319-03897-1
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)0302-9743

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

Cite this