R OMAN DOMINATION : a parameterized perspective†
Henning Fernau · International Journal of Computer Mathematics · 2007
We analyse the graph-theoretic formalization of ROMAN DOMINATION, dating back to the military strategy of the Emperor Constantine, from a parameterized perspective. More specifically, we prove that this problem is W[2]-complete for general graphs. However, parameterized algorithms are presented for graphs of bounded treewidth and for planar graphs. Moreover, it is shown that a parametric dual of ROMAN DOMINATION is in ℱ𝒫𝒯.