Roman domination on subclasses of bipartite graphs

The Roman Domination Problem (RDP) on a simple, finite, undirected graph $G=(V,E)$ asks for a labeling function $f:V\to \{0,1,2\}$ such that every vertex assigned value $0$ is adjacent to at least one vertex assigned value $2$. The objective is to minimize the total weight ${\sum }_{v\in V}f(v)$, and this minimum value is called the Roman domination number of $G$, denoted by ${\gamma }_R(G)$. Since the RDP is NP-complete for bipartite graphs, a natural direction is to study its complexity on restricted subclasses of bipartite graphs. The problem remains NP-complete even under strong structural restrictions, such as star-convex and comb-convex bipartite graphs. Therefore, identifying the borderline subclasses where the problem changes from NP-complete to polynomial-time solvable remains an important challenge. In this paper, we investigate the RDP on convex bipartite graphs and on their superclass, chordal bipartite graphs. First, we present a dynamic programming algorithm for convex bipartite graphs. The algorithm uses the interval ordering of one bipartition class and keeps a compact boundary state, which is sufficient to control the domination requirements of both processed and future vertices. This gives an $O(n^3)$-time algorithm for computing ${\gamma }_R(G)$ on an $n$ vertex convex bipartite graph. In contrast, we prove that the decision version of the RDP is NP-complete on chordal bipartite graphs by a polynomial reduction from $\text{textsc}DominatingSet$ on chordal bipartite graphs. Thus, our results show a clear separation between the tractability of convex bipartite graphs and the hardness of the larger chordal bipartite class.