Efficient Implementation of Dynamic Programming with Representative Sets

Abstract

In the rank based approach introduced by Bodlaender et al. the notion of representative sets is applied to dynamic programming algorithms for connectivity problems parameterized by treewidth. In this approach the tables in which partial solutions are stored are intermittently reduced in size. This results in a speed-up of these algorithms yielding running times single exponential in treewidth. We build this thesis upon earlier work, given an experimental study of these algorithms. In particular, we previously compared the performance of a classic dynamic programming algorithm for Steiner Tree with the performance of its counterpart in which the rank-based approach is applied. The fi?rst contribution of the thesis is an alternative representation of the partial solutions generated during the dynamic programming, with which we can eliminate a computational step of the reductions that is expensive in practice. We discuss the adaption of operators introduced in the framework by Bodlaender et al. in order to apply them to this new representation. This allows us to use the new representation for any of the connectivity problems for which a dynamic programming algorithm can be described using these operators. In an experimental evaluation for Steiner Tree we ?find that this representation yields very positive results. The second contribution of the thesis is an algorithm which calculates partial solutions in order of optimality instead of calculating entire tables at a time. We do this in order to avoid calculating partial solutions that do not contribute to the optimal solution of the full problem. We give a detailed description of this algorithm for Steiner Tree and perform an experimental evaluation. We find some mixed results, where the algorithm performs well in a few instances and badly in others.