Exact Exponential-Time and Treewidth-Based Algorithms for Defence-like Domination Problems

Abstract

Defence-like domination problems are variants to Dominating Set, where the goal is to defend a graph against attacks using guards. This is done by moving guards along edges in our graph in a response to these attacks. In this thesis we will define our own general definition of defence-like domination problems and present exact exponential-time and treewidth-based algorithms for a selection of these problems. Specifically we present an O*(4^n) time algorithm for k-Turn Defensive Domination, which is a problem newly introduced in this thesis. Next we present treewidth-based algorithms for Roman Domination, Weak Roman Domination and Secure Domination. These are all problems that have been studied extensively. For Roman Domination we present an O*(3^t) time algorithm for graphs of treewidth t. This is an improvement on the current literature. For Weak Roman Domination and Secure Domination we present an O*(9^t) time and O*(8^t) time algorithm respectively for graphs of treewidth t. To our knowledge these results are the first treewidth-based algorithms for these problems.