Abstract
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 ℱ𝒫𝒯.
†A preliminary version of this paper appeared in Proceedings of SOFSEM (2006).
Notes
†A preliminary version of this paper appeared in Proceedings of SOFSEM (2006).