New complexity results on Roman {2}-domination

LEONI, V.; FERNÁNDEZ, LARA

RAIRO - RECHERCHE OPERATIONNELLE (OPERATIONS RESEARCH)

EDP SCIENCES S A

Lugar: Paris; Año: 2023 vol. 57 p. 1905 - 1912

0399-0559

The study of a variant of Roman domination was initiated by Chellali et al. (2016). Given a graph $G$ with vertex set $V$, a Roman ${2}$-dominating function $f : V ightarrow {0, 1, 2}$ has the property that for every vertex $vin V$ with $f(v) =0$, either there exists a vertex $u$ adjacent to $v$ with $f(u) = 2$, or at least two vertices $x,; y$ adjacent to $v$ with $f(x)=f(y)=1$. The weight of a Roman ${2}$-dominating function is the value $f(V) = sum_{vin V} f(v)$. The minimum weight of a Roman ${2}$-dominating function is called the Roman ${2}$-domination number and is denoted by $gamma_{{R2}}(G)$. In this work we find several NP-complete instances of the Roman ${2}$-domination problem: chordal graphs, bipartite planar graphs, chordal bipartite graphs, bipartite with maximum degree 3 graphs, among others. A result by Chellali et al. (2016) shows that $gamma_{{R2}}(G)$ and the 2-rainbow domination number of $G$ coincide when $G$ is a tree, and thus, the linear time algorithm for $k$-rainbow domination due to Bresar et al. (2008) can be followed to compute $gamma_{{R2}}(G)$. In this work we develop an efficient algorithm that is independent of $k$-rainbow domination and computes the Roman ${2}$-domination number on a subclass of trees called caterpillars.