Extension Perfect Roman Domination
摘要
For an introductory single lecture into parameterized complexity classes, it appears to be necessary to introduce different problems to capture the (most important) different levels of the W-hierarchy. This puts an additional burden on the audience, as they also have to understand the different problems and not only the different complexity classes. In this paper, we will show that Extension Perfect Roman Domination, \(\textsc {Ext PRD}\) for short, is a single problem that can be used for this introductory purpose. We can characterize the classes \(\textsf {W}[1]\) , \(\textsf {W}[2]\) and \(\textsf {W}[3]\) and find problems in FPT, XP and those being para-NP-hard. Also, it can be used to explain how the choice of the parameter can influence the complexity status of the problem. One can even touch fine-grained complexity by establishing a run-time lower bound based on the k-Orthogonal Vector conjecture. Ext PRD, being a sibling to Roman Domination, also comes with a nice story that can be also seen from the perspective of adventure games and might hence be appealing.