ROMAN DOMINATION: a parameterized perspective†

†A preliminary version of this paper appeared in Proceedings of SOFSEM (2006).

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).

Keywords:

• Fixed-parameter tractability and intractability
• Domination problems in graphs

Notes

†A preliminary version of this paper appeared in Proceedings of SOFSEM (2006).

Additional information

Notes on contributors

Henning Fernau

Email: [email protected]