A Dynamic Programming Approach to the Dominating Set Problem on k -Trees

Dynamic programming has long been established as an important technique for demonstrating the existence of polynomial time algorithms for various discrete optimization problems. In this paper we extend the normal paradigm of dynamic programming to allow a polynomial number of optimal solutions to be computed for each subproblem. This technique yields a polynomial time algorithm for the dominating set problem on k-trees, where k is fixed. It is also shown that the dominating set problem is NP-complete for k-trees where k is arbitrary.