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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Extension Perfect Roman Domination

  • Kevin Mann,
  • Henning Fernau

摘要

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.