The Parameterized Complexity of Roman Domination Reconfiguration

Abstract

In this thesis, we prove the W[2]-completeness of Roman Domination Reconfiguration, parameterized by the number of tokens used and the length of the Reconfiguration sequence, under both the Token Jumping and the Token Sliding rule. We discuss the individual concepts of Roman Domination, Reconfiguration, and parameterized complexity separately, before combining these notions and presenting our proofs and the subsequent results. Interestingly, the reduction we used for our hardness proofs was a reduction from parameterized Dominating Set, while one might expect a reduction from Dominating Set Reconfiguration to be a more likely candidate.