Domination problems on P₅-free graphs^∗

Intendente Güiraldes 2160, C1428EGA Buenos Aires, Buenos Aires Province, Argentina
oscarlin@dc.uba.ar; michel.mizrahi@gmail.com

Received: 28 March 2014
Accepted: 15 September 2014

Abstract

The minimum roman dominating problem (denoted by γ_R(G), the weight of minimum roman dominating function of graph G) is a variant of the very well known minimum dominating set problem (denoted by γ(G), the cardinality of minimum dominating set of graph G). Both problems remain NP-Complete when restricted to P₅-free graph class [A.A. Bertossi, Inf. Process. Lett. 19 (1984) 37–40; E.J. Cockayne, et al. Discret. Math. 278 (2004) 11–22]. In this paper we study both problems restricted to some subclasses of P₅-free graphs. We describe robust algorithms that solve both problems restricted to (P₅,(s,t)-net)-free graphs in polynomial time. This result generalizes previous works for both problems, and improves existing algorithms when restricted to certain families such as (P₅,bull)-free graphs. It turns out that the same approach also serves to solve problems for general graphs in polynomial time whenever γ(G) and γ_R(G) are fixed (more efficiently than naive algorithms). Moreover, the algorithms described are extremely simple which makes them useful for practical purposes, and as we show in the last section it allows to simplify algorithms for significant classes such as cographs.