Speeding up dynamic programming with representative sets: An experimental evaluation of algorithms for Steiner tree on tree decompositions

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)
251 Downloads (Pure)

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. (Proceedings of the 40th international colloquium on automata, languages and programming, ICALP 2013, part I, volume 7965 of Lecture Notes in Computer Science. Springer, Berlin, pp 196–207, 2013), 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 that 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. Our comparison of the classic dynamic programming algorithm and the improved dynamic programming algorithm that employs 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. Thus, the rank-based approach from Bodlaender et al. (2013) 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. Furthermore, we propose an alternative representation of partial solutions using weighted bit strings in order to circumvent a part of the reduction step that is computationally expensive in practice. In the experimental evaluation we find that this representation yields further significant improvements. We show that the representation can also be used for the other problems fitting in the framework of Bodlaender et al. (2013). Keywords: Experimental evaluation; Algorithmic engineering; Steiner tree; Treewidth; Dynamic programming; Exact algorithms
Original languageEnglish
Pages (from-to)636-660
Number of pages25
JournalAlgorithmica
Volume71
Issue number3
DOIs
Publication statusPublished - 2015

Fingerprint Dive into the research topics of 'Speeding up dynamic programming with representative sets: An experimental evaluation of algorithms for Steiner tree on tree decompositions'. Together they form a unique fingerprint.

Cite this