Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Informatik

Abstract der Arbeit:

In this thesis, we study algorithms for computing the domination polynomial of a graph of bounded treedepth given an associated elimination tree. We describe three dynamic-programming approaches that process the tree bottom-up and combine partial dominating-set counts for subtrees. The first method is a direct naive recurrence, the second adds memoisation to avoid some repeated work, and the third is a more advanced algorithm following the subset-convolution based framework of Pilipczuk and Wrochna.
We explain the state space, recurrence relations, and implementation details for all three approaches, with a focus on space-efficient representations in C++. We evaluate the implementations experimentally on random graphs parameterised by treedepth, number of vertices, and edge probability, comparing runtime and memory usage. The results show that the naive method quickly becomes impractical for larger instances, while the memoised and third methods improve the runtime substantially. In the experimental setting, the measured peak heap memory is dominated by the representation of the input graph and elimination tree, so the differences between the algorithms are minor compared with the input size itself. Overall, this thesis demonstrates how bounded-treedepth structure can be exploited to obtain polynomial-space algorithms for counting dominating sets efficiently and provides evidence for the practical performance of the resulting methods.