Keywords. Roman domination, Roman-\(\{2\}\) domination, Double Roman domination; Perfect Roman domination, Unique response Roman domination, Convex bipartite graph, Chordal bipartite graph, Dynamic programming, NP-completeness

1 Introduction↩︎

Domination is one of the central and most extensively studied topics in graph theory and graph algorithms. A set \(D\subseteq V(G)\) is a dominating set of a graph \(G\) if every vertex in \(V(G)\setminus D\) has a neighbour in \(D\). Although the definition is simple, domination and its numerous variants provide natural models for facility location, network monitoring, communication systems, resource allocation, and protection problems. We refer to the standard monographs [1]–[3] for a comprehensive treatment of domination in graphs.

Roman domination is a weighted form of domination motivated by the problem of deploying a limited number of military units to protect the regions of the Roman Empire. The historical motivation was popularized by Stewart [4] and discussed mathematically by ReVelle and Rosing [5]. The graph-theoretic notion was formally introduced by Cockayne et al. [6]. A Roman dominating function, abbreviated as an RDF, of a graph \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) has a neighbour assigned value \(2\). The weight of \(f\) is \(w(f)=\sum_{v\in V(G)}f(v)\), and the minimum possible weight is the Roman domination number \(\gamma_R(G)\).

The value \(2\) may be interpreted as placing two units of defence at a vertex. One unit protects the vertex itself, while the second unit can be moved to an adjacent undefended vertex when necessary. A vertex assigned value \(1\) has enough defence only for itself, whereas a vertex assigned value \(0\) must rely on a neighbouring vertex assigned value \(2\). Since the introduction of the parameter, Roman domination has been studied from structural, extremal, algorithmic, and complexity-theoretic viewpoints; see, for example, [7]–[10]. Many variants have also been introduced by changing the permitted values or strengthening the local protection requirements.

In this paper, we consider four such variants: Roman-\(\{2\}\) domination, double Roman domination, perfect Roman domination, and unique response Roman domination. Although their local feasibility conditions are different, we show that all four problems can be treated by a common left-to-right dynamic programming framework on convex bipartite graphs.

1.1 The Roman-type domination parameters↩︎

Roman-\(\{2\}\)omination.

Roman-\(\{2\}\) domination was introduced by Chellali et al. [11]. A Roman-\(\{2\}\) dominating function of a graph \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex \(v\) with \(f(v)=0\) satisfies \(\sum_{u\in N(v)}f(u)\geq 2\). Thus, a vertex assigned value \(0\) may be protected either by one neighbour assigned value \(2\), or by at least two neighbours assigned value \(1\). The minimum weight of such a function is the Roman-\(\{2\}\) domination number, denoted by \(\gamma_{\{R2\}}(G)\).

This parameter is also commonly studied under the name Italian domination. In contrast with ordinary Roman domination, two vertices carrying one unit of defence each may cooperate to protect an undefended vertex. Fundamental structural properties were established by Chellali et al. [11], while Italian domination on trees was studied by Henning and Klostermeyer [12]. Complexity and algorithmic questions for Roman-\(\{2\}\) domination were subsequently investigated by Chen and Lu [13] and by Padamutham and Palagiri [14]. Despite this progress, its complexity remained unsettled on several structured bipartite graph classes.

Double Roman domination.

Double Roman domination was introduced by Beeler, Haynes, and Hedetniemi [15]. A double Roman dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2,3\}\) such that every vertex assigned value \(0\) has either a neighbour assigned value \(3\), or at least two neighbours assigned value \(2\), and every vertex assigned value \(1\) has a neighbour assigned value \(2\) or \(3\). The minimum weight of such a function is the double Roman domination number \(\gamma_{dR}(G)\).

Double Roman domination models a stronger defence requirement than ordinary Roman domination. A vertex assigned value \(3\) can provide the complete defence required by an adjacent zero vertex, while two neighbours assigned value \(2\) may jointly provide the same protection. Beeler et al. [15] proved the useful fact that every graph has a minimum double Roman dominating function in which no vertex is assigned value \(1\). Therefore, when designing an optimization algorithm, it is sufficient to consider the values \(0\), \(2\), and \(3\). Further structural, complexity, and algorithmic results were obtained by Banerjee et al. [16], Yue et al. [17], and Poureidi [18].

Perfect Roman domination.

A perfect Roman dominating function of a graph \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) has exactly one neighbour assigned value \(2\). The minimum weight of such a function is the perfect Roman domination number, denoted by \(\gamma_R^p(G)\). Thus, perfect Roman domination strengthens ordinary Roman domination by replacing the requirement of at least one value-\(2\) neighbour with an exact-one requirement.

Perfect Roman domination was studied on trees by Henning et al. [19]. Banerjee et al. [20] later developed a broader algorithmic and complexity study of the problem and established results on several restricted graph classes. The exactness requirement makes the problem algorithmically different from ordinary Roman domination. Once a zero vertex has acquired a value-\(2\) neighbour, every subsequent choice must ensure that it does not acquire a second one. Consequently, a dynamic program must retain information about both undominated zero vertices and zero vertices whose protection has already been completed.

Unique response Roman domination.

The unique response form of Roman domination originates in the Roman influence parameters introduced by Rubalcaba and Slater [21]. It was subsequently studied by Targhi et al. [22]. A unique response Roman dominating function, abbreviated as a URRDF, is a Roman dominating function \(f:V(G)\rightarrow\{0,1,2\}\) satisfying the following additional conditions: every vertex assigned value \(0\) has exactly one neighbour assigned value \(2\), and every vertex assigned value \(1\) or \(2\) has no neighbour assigned value \(2\). The minimum weight of a URRDF is the unique response Roman domination number \(u_R(G)\).

The first condition guarantees that every undefended vertex has a unique possible responder. The second condition prevents a vertex assigned value \(2\) from being adjacent to any positive vertex, including another value-\(2\) vertex. Hence, the set of value-\(2\) vertices forms a highly restricted packing. Relations between Roman domination and the unique response Roman domination were studied by Targhi et al. [22], while trees satisfying \(\gamma_R(G)=u_R(G)\) were investigated by Jafari Rad and Liu [23]. Zhao et al. [24] provided further results for trees and proved hardness on triangle-free graphs.

A detailed algorithmic study of unique response Roman domination was recently given by Banerjee et al. [25]. They proved that the decision problem is NP-complete on chordal graphs and on bipartite graphs, established strong inapproximability results, and gave polynomial-time algorithms for distance-hereditary graphs, interval graphs, and proper interval graphs. In particular, they obtained a linear-time algorithm for distance-hereditary graphs, a polynomial-time algorithm for interval graphs, and a linear-time algorithm for proper interval graphs.

1.2 Structured bipartite graph classes and motivation↩︎

We study the four parameters on convex bipartite graphs and chordal bipartite graphs. A bipartite graph \(G=(X\cup Y,E)\) is convex with respect to \(X\) if there is a linear ordering \(X=\{x_1,\ldots,x_m\}\) such that the neighbourhood of every vertex of \(Y\) is an interval in this ordering. Thus, for every \(y\in Y\), there exist indices \(l(y)\) and \(r(y)\) such that \(N(y)=\{x_{l(y)},\ldots,x_{r(y)}\}\). The interval representation gives a strong left-to-right ordering that is well-suited to dynamic programming.

A bipartite graph is chordal bipartite if it contains no induced cycle of length at least \(6\). Convex bipartite graphs form a structured subclass of chordal bipartite graphs, but a general chordal bipartite graph need not admit a convex ordering. Consequently, the two classes provide a natural setting for studying the effect of an interval ordering on the complexity of Roman-type domination. Standard structural information about these and related graph classes can be found in [26].

For ordinary Roman domination, polynomial-time algorithms are known on several graph classes possessing suitable ordering or decomposition properties [8]–[10]. More recently, Das et al. [27] studied Roman domination specifically on subclasses of bipartite graphs. They gave an \(O(n^3)\)-time algorithm for convex bipartite graphs and proved that the problem is NP-complete on chordal bipartite graphs. These results reveal a sharp algorithmic contrast between the interval structure of convex bipartite graphs and the weaker induced-cycle restriction defining chordal bipartite graphs. The present paper investigates whether the same contrast persists for stronger Roman-type parameters.

The complexity table of Banerjee et al. [25] provides additional motivation for our study. Their table records Roman-\(\{2\}\) domination, perfect Roman domination, and unique response Roman domination as open on chordal bipartite graphs. Double Roman domination was already known to be NP-complete on chordal bipartite graphs [16]. The same table records Roman-\(\{2\}\), double Roman, perfect Roman, and unique response Roman domination as open on bipartite permutation graphs. Since every bipartite permutation graph is biconvex and hence convex bipartite, a polynomial-time algorithm for convex bipartite graphs settles all four of these open entries in the stronger convex-bipartite setting.

It is important to distinguish these statements carefully. Convex bipartite graphs were not listed as a separate row in the table of Banerjee et al. [25]. However, their open cases for bipartite permutation graphs are covered by our more general convex-bipartite algorithms. On the hardness side, their table explicitly left the Roman-\(\{2\}\), perfect Roman, and unique response Roman problems open on chordal bipartite graphs, and these are precisely the three chordal bipartite cases settled in this paper.

1.3 Our Contributions↩︎

Our first contribution is a unified dynamic programming framework for Roman-\(\{2\}\) domination, double Roman domination, perfect Roman domination, and unique response Roman domination on convex bipartite graphs. Let \(G=(X\cup Y,E)\) be convex with respect to the ordering \(X=\{x_1,\ldots,x_m\}\). For every \(y\in Y\), write \(N(y)=\{x_{l(y)},\ldots,x_{r(y)}\}\), and define \(Y_i=\{y\in Y:r(y)=i\}\). The algorithm processes the graph in the order \(x_1,Y_1,x_2,Y_2,\ldots,x_m,Y_m\).

When a vertex \(y\in Y_i\) is processed, all its neighbours have already been processed, and its neighbourhood \(N(y)=\{x_{l(y)},\ldots,x_i\}\) is a suffix of the currently processed part of \(X\). This suffix property allows the unfinished requirements of the processed vertices to be compressed into a constant number of boundary indices. The interpretation of the indices depends on the variant. For Roman-\(\{2\}\) and double Roman domination, the state records unresolved deficits of processed zero vertices. For a perfect Roman and a unique response Roman domination, it records active vertices that still need a value-\(2\) neighbour together with the vertices that must not be reached by another value-\(2\) vertex.

Although the four state spaces are different, they all contain five coordinates, each having \(O(n)\) possible values. Every vertex is processed once, and every transition takes constant time. Consequently, each of the four parameters can be computed in \(O(n^6)\) time and \(O(n^5)\) space on an \(n\)-vertex convex bipartite graph. Since biconvex bipartite graphs and bipartite permutation graphs are subclasses of convex bipartite graphs, these algorithms also establish polynomial-time solvability on both of these subclasses.

Our second contribution is a collection of hardness results for chordal bipartite graphs. We prove that Roman-\(\{2\}\) domination is NP-complete on chordal bipartite graphs by a reduction from Dominating Set on chordal bipartite graphs, which is known to be NP-complete [28]. We prove that unique response Roman domination is NP-complete on chordal bipartite graphs by a reduction based on Efficient Domination; the required hardness result for efficient domination follows from the work of Lu and Tang [29]. Finally, we establish the NP-completeness of perfect Roman domination on chordal bipartite graphs using a separate edge gadget that enforces the independence condition required by the reduction.

These results settle the chordal-bipartite entries that were explicitly listed as open for Roman-\(\{2\}\), perfect Roman, and unique response Roman domination in the complexity table of Banerjee et al. [25]. Together with the existing hardness of double Roman domination on chordal bipartite graphs completes the complexity classification of the four variants considered here on chordal bipartite graphs. At the same time, the convex-bipartite algorithms settle the open bipartite-permutation cases recorded in the same table.

Therefore, our results establish a clear tractability–hardness contrast. The interval ordering of convex bipartite graphs permits the unfinished local conditions to be represented by compact boundary information, leading to polynomial-time algorithms. By contrast, excluding induced cycles of length at least \(6\) does not provide enough structure to make the same problems tractable on chordal bipartite graphs.

The remainder of the paper is organized as follows. Section 2 introduces the necessary definitions and notation. Section 3 presents the unified dynamic programming framework for the four Roman-type domination problems on convex bipartite graphs. Section 4 establishes the NP-completeness results for Roman-\(\{2\}\), perfect Roman, and unique response Roman domination on chordal bipartite graphs. Section 5 concludes the paper and discusses directions for further research.

2 Preliminaries↩︎

In this section, we recall the graph-theoretic terminology and the Roman-type domination parameters used throughout the paper. All graphs considered in this paper are finite, simple, and undirected. For a graph \(G\), we denote its vertex set and edge set by \(V(G)\) and \(E(G)\), respectively. For a vertex \(v\in V(G)\), the open neighborhood of \(v\) is \(N_G(v)=\{u\in V(G):uv\in E(G)\}\), and the closed neighborhood is \(N_G[v]=N_G(v)\cup\{v\}\). When the graph is clear from the context, we simply write \(N(v)\) and \(N[v]\).

A set \(D\subseteq V(G)\) is a dominating set of \(G\) if every vertex in \(V(G)\setminus D\) has a neighbour in \(D\). The minimum cardinality of a dominating set of \(G\) is the domination number of \(G\), denoted by \(\gamma(G)\). A set \(D\subseteq V(G)\) is an efficient dominating set if every vertex \(v\in V(G)\) satisfies \(|N_G[v]\cap D|=1\).

A Roman dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex \(v\) with \(f(v)=0\) has at least one neighbor \(u\) with \(f(u)=2\). The weight of \(f\) is \(w(f)=\sum_{v\in V(G)}f(v)\). The Roman domination number of \(G\), denoted by \(\gamma_R(G)\), is the minimum weight of a Roman dominating function of \(G\).

A Roman-\(\{2\}\) dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex \(v\) with \(f(v)=0\) satisfies \(\sum_{u\in N(v)}f(u)\geq 2\). The Roman-\(\{2\}\) domination number of \(G\), denoted by \(\gamma_{\{R2\}}(G)\), is the minimum weight of such a function.

A double Roman dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2,3\}\) such that every vertex assigned value \(0\) has either a neighbour assigned value \(3\), or at least two neighbours assigned value \(2\), and every vertex assigned value \(1\) has a neighbour assigned value \(2\) or \(3\). The double Roman domination number of \(G\), denoted by \(\gamma_{dR}(G)\), is the minimum weight of a double Roman dominating function. We use the standard fact that every graph has a minimum double Roman dominating function using no vertex of value \(1\).

A perfect Roman dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) has exactly one neighbour assigned value \(2\). The perfect Roman domination number of \(G\), denoted by \(\gamma_R^p(G)\), is the minimum weight of a perfect Roman dominating function.

A unique response Roman dominating function of \(G\) is a Roman dominating function \(f:V(G)\rightarrow\{0,1,2\}\) with the following additional restrictions: every vertex assigned value \(0\) has exactly one neighbour assigned value \(2\), and every vertex assigned value \(1\) or \(2\) has no neighbor assigned value \(2\). The unique response Roman domination number of \(G\) is denoted by \(u_R(G)\).

A bipartite graph \(G=(X\cup Y,E)\) is convex with respect to \(X\) if there exists a linear ordering \(X=\{x_1,x_2,\ldots,x_m\}\) such that, for every \(y\in Y\), the neighborhood of \(y\) is an interval in this ordering. Thus, for every \(y\in Y\), there exist integers \(l(y)\) and \(r(y)\), with \(1\leq l(y)\leq r(y)\leq m\), such that \(N(y)=\{x_{l(y)},x_{l(y)+1},\ldots,x_{r(y)}\}\). Throughout the algorithmic section, we assume that such a convex ordering and the interval endpoints \(l(y)\) and \(r(y)\) are given. For each \(i\in\{1,\ldots,m\}\), we write \(Y_i=\{y\in Y:r(y)=i\}\).

A bipartite graph is chordal bipartite if it has no induced cycle of length at least six. Equivalently, every induced cycle in a chordal bipartite graph has length four. Chordal bipartite graphs strictly generalize several structured bipartite graph classes, but they do not necessarily admit the interval ordering used in convex bipartite graphs. This distinction is important in this paper: the interval structure of convex bipartite graphs leads to polynomial-time algorithms, while the broader chordal bipartite class remains hard for several Roman-type domination problems.

For each Roman-type parameter considered in this paper, the corresponding decision problem asks whether the graph admits a feasible function of weight at most a given integer \(K\). Since a proposed function can be checked in polynomial time, all these decision problems belong to \(\mathsf{NP}\).

3 A Unified Dynamic Programming Framework for Roman-Type Domination in Convex Bipartite Graphs↩︎

In this section, we show that the left-to-right dynamic programming method used for ordinary Roman domination on convex bipartite graphs can be extended to four related Roman-type domination parameters. The four parameters considered here are Roman-\(\{2\}\) domination, double Roman domination, perfect Roman domination, and unique response Roman domination. Although their local feasibility conditions are different, all four algorithms use the same structural principle: the graph is processed from left to right along a convex ordering of one bipartition class, and the unfinished requirements of already processed vertices are represented by a constant number of boundary indices.

3.1 Convex Ordering and Processing Order↩︎

Let \(G=(X\cup Y,E)\) be a bipartite graph, where \(X=\{x_1,x_2,\ldots,x_m\}\) is given in a fixed linear order. We assume that \(G\) is convex with respect to \(X\). Thus, for every vertex \(y\in Y\), the neighbourhood of \(y\) is an interval in the ordering of \(X\), and we write \(N(y)=\{x_{l(y)},x_{l(y)+1},\ldots,x_{r(y)}\}\). For each \(i\in\{1,\ldots,m\}\), let \(Y_i=\{y\in Y:r(y)=i\}\).

The vertices are processed in the order \(x_1,Y_1,x_2,Y_2,\ldots,x_m,Y_m\). Inside each set \(Y_i\), the vertices may be processed in an arbitrary but fixed order. When a vertex \(y\in Y_i\) is processed, all its neighbours have already been processed, and its neighbourhood is \(N(y)=\{x_{l(y)},\ldots,x_i\}\). Therefore, the neighbourhood of \(y\) is a suffix of the currently processed part \(\{x_1,\ldots,x_i\}\) of \(X\). This suffix property is the central structural reason why the unfinished requirements of processed vertices of \(X\) can be compressed into a small number of indices.

For a fixed algorithm, the table \(D\) stores the minimum weight of a feasible partial assignment for every state that can occur after the part of the graph processed so far. We use \(p_\infty=m+1\) as a special state value, meaning that the corresponding vertex does not exist. The symbol \(+\infty\), on the other hand, denotes an infeasible table entry. A state \(\sigma\) is called finite if \(D(\sigma)<+\infty\). Whenever a new vertex is processed, a temporary table \(D'\) is initialized with the value \(+\infty\) in every entry. All feasible transitions from the current table \(D\) are written into \(D'\), and then \(D'\) replaces \(D\). The instruction “update \(D'(\sigma')\) with \(w\)” means that \(D'(\sigma')\) is replaced by \(\min\{D'(\sigma'),w\}\).

For every variant, all already processed vertices of \(Y\) must completely satisfy their domination condition. Indeed, when \(y\in Y_i\) is processed, all vertices of \(N(y)\) have already been assigned values, and no future vertex can change the contribution received by \(y\). In contrast, a processed vertex of \(X\) assigned value \(0\) may still receive a contribution from a future vertex of \(Y\). Consequently, the states store unfinished information only for processed vertices of \(X\).

3.2 A Common Deficit Representation↩︎

Roman-\(\{2\}\) domination and double Roman domination use the same form of unfinished information. In both cases, a processed vertex \(x_t\in X\) assigned value \(0\) may still need either two units or one unit of contribution from future vertices of \(Y\). We say that \(x_t\) has deficit \(2\) if it has not yet received any useful contribution, and that it has deficit \(1\) if it has received one useful unit but is not yet safe.

The state stores two indices \(a\) and \(b\). The value \(a\) is the smallest index of a processed vertex of \(X\) having deficit \(2\); if no such vertex exists, then \(a=p_\infty\). If \(a\neq p_\infty\), then \(b\) is the smallest index of a deficit-\(1\) vertex lying strictly before \(a\); if no such vertex exists, then \(b=p_\infty\). Deficit-\(1\) vertices at or after \(a\) do not need to be recorded separately. If \(a=p_\infty\), then \(b\) is simply the smallest index of any deficit-\(1\) vertex, or \(p_\infty\) if no such vertex exists.

The reason this compressed pair is sufficient is the suffix property. Suppose that \(x_a\) is the earliest deficit-\(2\) vertex. Every future vertex of \(Y\) that reaches \(x_a\) also reaches every later processed vertex of \(X\). Hence, as long as \(x_a\) remains unfinished, the detailed status of later deficient vertices does not affect any future feasibility decision. The only deficit-\(1\) vertex that may behave differently is one lying before \(a\), and it is enough to store the earliest such vertex in \(b\). When no deficit-\(2\) vertex remains, the earliest deficit-\(1\) vertex alone determines whether a future suffix update clears all remaining deficits.

We use two constant-time update operations on the pair \((a,b)\). The operation \(\operatorname{Reduce}(a,b,l)\) is applied when a processed vertex \(y\in Y_i\) gives one useful unit to every unfinished vertex in the suffix \(\{x_l,\ldots,x_i\}\). The operation \(\operatorname{Clear}(a,b,l)\) is applied when \(y\) gives enough contribution to make every unfinished vertex in that suffix safe.

For \(\operatorname{Reduce}(a,b,l)\), the following cases apply.

1. If \(a=p_\infty\), then only deficit-\(1\) vertices may remain. If \(b<l\), the earliest such vertex is outside the suffix and the new pair is \((p_\infty,b)\). If \(b\geq l\), every deficit-\(1\) vertex lies in the suffix and becomes safe, so the new pair is \((p_\infty,p_\infty)\).

2. If \(a\neq p_\infty\) and \(a<l\), the earliest deficit-\(2\) vertex is outside the suffix. It remains the controlling unfinished vertex, and the new pair is \((a,b)\).

3. If \(a\neq p_\infty\) and \(a\geq l\), every deficit-\(2\) vertex lies in the suffix and is reduced to deficit \(1\). If \(b<l\), the previously stored deficit-\(1\) vertex remains the earliest one, so the new pair is \((p_\infty,b)\). Otherwise, the vertex \(x_a\) becomes the earliest remaining deficit-\(1\) vertex, and the new pair is \((p_\infty,a)\).

For \(\operatorname{Clear}(a,b,l)\), the following cases apply.

1. If \(a=p_\infty\), then the new pair is \((p_\infty,b)\) when \(b<l\), and \((p_\infty,p_\infty)\) otherwise.

2. If \(a\neq p_\infty\) and \(a<l\), the earliest deficit-\(2\) vertex is not reached, and the new pair remains \((a,b)\).

3. If \(a\neq p_\infty\) and \(a\geq l\), every deficit-\(2\) vertex is cleared. If \(b<l\), the stored deficit-\(1\) vertex remains unfinished and the new pair is \((p_\infty,b)\). Otherwise, every unfinished vertex is cleared, and the new pair is \((p_\infty,p_\infty)\).

Thus, \(\operatorname{Reduce}\) lowers by one the unfinished requirements reached by the current suffix, whereas \(\operatorname{Clear}\) removes all unfinished requirements reached by that suffix.

3.3 Roman-\(\{2\}\) Domination↩︎

A Roman-\(\{2\}\) dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex \(v\) with \(f(v)=0\) satisfies \(\sum_{u\in N(v)}f(u)\geq 2\). The weight of \(f\) is \(w(f)=\sum_{v\in V(G)}f(v)\), and the Roman-\(\{2\}\) domination number is denoted by \(\gamma_{\{R2\}}(G)\).

A zero vertex can be protected either by one neighbour of value \(2\), or by at least two neighbours of value \(1\). Therefore, when a vertex \(y\in Y_i\) is processed, the algorithm must know whether its interval contains a value-\(2\) vertex of \(X\), or at least two value-\(1\) vertices of \(X\).

State.

A state is a tuple \((r,u,v,a,b)\). The coordinate \(r\) is the largest index of a processed vertex of \(X\) assigned value \(2\); if no such vertex exists, then \(r=0\). The coordinates \(u\) and \(v\) are respectively the largest and second largest indices of processed vertices of \(X\) assigned value \(1\); a missing index is represented by \(0\). The pair \((a,b)\) stores the deficit information defined above.

For a finite state \((r,u,v,a,b)\), the table value \(D(r,u,v,a,b)\) is the minimum weight of a feasible partial Roman-\(\{2\}\) assignment realizing these five boundary values. Feasibility means that every processed vertex of \(Y\) assigned value \(0\) already receives a total neighbour value at least \(2\), while every unfinished processed vertex of \(X\) is represented by \((a,b)\).

The initial state is \((0,0,0,p_\infty,p_\infty)\) with table value \(0\). A final state is accepting exactly when \(a=b=p_\infty\), because then every processed zero vertex of \(X\) has received total contribution at least \(2\).

Processing a vertex of \(X\)

Suppose that \(x_i\) is processed from a finite state \((r,u,v,a,b)\).

1. If \(f(x_i)=0\), then \(x_i\) initially has deficit \(2\), since no previously processed vertex of \(Y\) is adjacent to \(x_i\). If \(a=p_\infty\), set \(a_0=i\); otherwise set \(a_0=a\). The new state is \((r,u,v,a_0,b)\), with no increase in weight.

2. If \(f(x_i)=1\), then \(x_i\) is safe and becomes the newest value-\(1\) vertex of \(X\). The new state is \((r,i,u,a,b)\), and the weight increases by \(1\).

3. If \(f(x_i)=2\), then \(x_i\) is safe and becomes the newest value-\(2\) vertex of \(X\). The new state is \((i,u,v,a,b)\), and the weight increases by \(2\).

Processing a vertex of \(Y\)

Let \(y\in Y_i\), and write \(l=l(y)\). Then \(N(y)=\{x_l,\ldots,x_i\}\).

1. If \(f(y)=0\), then \(y\) must receive a total neighbour value at least \(2\). The interval contains a value-\(2\) vertex exactly when \(r\geq l\), and it contains at least two value-\(1\) vertices exactly when \(v\geq l\). Hence, the transition is feasible exactly when \(r\geq l\) or \(v\geq l\). In this case, the state and weight do not change.

2. If \(f(y)=1\), then \(y\) contributes one unit to every unfinished zero vertex of \(X\) in its interval. The deficit pair becomes \(\operatorname{Reduce}(a,b,l)\), and the weight increases by \(1\).

3. If \(f(y)=2\), then every unfinished zero vertex of \(X\) in its interval receives enough contribution to become safe. The deficit pair becomes \(\operatorname{Clear}(a,b,l)\), and the weight increases by \(2\).

3.4 Double Roman Domination↩︎

A double Roman dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2,3\}\) such that every vertex assigned value \(0\) has either a neighbour assigned value \(3\), or at least two neighbours assigned value \(2\), and every vertex assigned value \(1\) has a neighbour assigned value \(2\) or \(3\). The double Roman domination number is denoted by \(\gamma_{dR}(G)\).

We use the standard observation that every graph has a minimum double Roman dominating function in which no vertex is assigned value \(1\). Indeed, if \(f(v)=1\) and \(v\) has a neighbour \(u\) of value \(3\), then changing \(v\) from \(1\) to \(0\) decreases the weight. If \(f(v)=1\) and \(v\) has a neighbour \(u\) of value \(2\), then changing \(v\) from \(1\) to \(0\) and \(u\) from \(2\) to \(3\) preserves the weight and decreases the number of vertices assigned value \(1\). Thus, among the minimum solutions, one may assume that only the values \(0\), \(2\), and \(3\) are used.

State.

A state is a tuple \((r_3,r_2,s_2,a,b)\). The coordinate \(r_3\) is the largest index of a processed vertex of \(X\) assigned value \(3\). The coordinates \(r_2\) and \(s_2\) are respectively the largest and second largest indices of processed vertices of \(X\) assigned value \(2\). Missing indices are represented by \(0\). The pair \((a,b)\) stores the unfinished double Roman requirements: deficit \(2\) means that a zero vertex has not yet received any value-\(2\) neighbour from \(Y\), while deficit \(1\) means that it has received one such neighbour but still needs either another value-\(2\) neighbour or a value-\(3\) neighbour.

The initial state is \((0,0,0,p_\infty,p_\infty)\) with value \(0\), and a final state is accepting exactly when \(a=b=p_\infty\).

Processing a vertex of \(X\)

Suppose that \(x_i\) is processed from a finite state \((r_3,r_2,s_2,a,b)\).

1. If \(f(x_i)=0\), then \(x_i\) starts with deficit \(2\). Thus, if \(a=p_\infty\), set \(a_0=i\); otherwise set \(a_0=a\). The new state is \((r_3,r_2,s_2,a_0,b)\).

2. If \(f(x_i)=2\), then \(x_i\) becomes the newest value-\(2\) vertex of \(X\). The new state is \((r_3,i,r_2,a,b)\), and the weight increases by \(2\).

3. If \(f(x_i)=3\), then \(x_i\) becomes the newest value-\(3\) vertex of \(X\). The new state is \((i,r_2,s_2,a,b)\), and the weight increases by \(3\).

Processing a vertex of \(Y\)

Let \(y\in Y_i\), and let \(l=l(y)\).

1. If \(f(y)=0\), then \(y\) must have either a value-\(3\) neighbour or two value-\(2\) neighbours. The first condition is equivalent to \(r_3\geq l\), and the second is equivalent to \(s_2\geq l\). Hence, this transition is feasible exactly when \(r_3\geq l\) or \(s_2\geq l\).

2. If \(f(y)=2\), then \(y\) gives one useful unit to every unfinished zero vertex of \(X\) in its interval. The deficit pair becomes \(\operatorname{Reduce}(a,b,l)\), and the weight increases by \(2\).

3. If \(f(y)=3\), then every unfinished zero vertex in its interval becomes safe. The deficit pair becomes \(\operatorname{Clear}(a,b,l)\), and the weight increases by \(3\).

3.5 Perfect Roman Domination↩︎

A perfect Roman dominating function of \(G\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) has exactly one neighbour assigned value \(2\). The perfect Roman domination number is denoted by \(\gamma_R^p(G)\).

For a processed vertex \(x_t\in X\) assigned value \(0\), we use two terms. The vertex \(x_t\) is active if it has not yet received any neighbour in \(Y\) assigned value \(2\). It is closed if it has already received exactly one such neighbour. A closed vertex must never be reached again by a future vertex of \(Y\) assigned value \(2\).

State.

A state is a tuple \((r_1,r_2,q,p,t)\). The coordinates \(r_1\) and \(r_2\) are respectively the largest and second largest indices of processed vertices of \(X\) assigned value \(2\); missing indices are represented by \(0\). The coordinate \(q\) is the largest index of a closed vertex of \(X\), and \(q=0\) if no closed vertex exists. The coordinates \(p\) and \(t\) are respectively the first and last active vertices of \(X\). If no active vertex exists, then \(p=t=p_\infty\).

The pair \((p,t)\) is sufficient because the suffix structure permits only three useful possibilities when a future value-\(2\) vertex of \(Y\) is processed: it reaches all active vertices, it reaches none of them, or it reaches only a proper suffix. The third possibility can never be extended to a perfect Roman dominating function. Indeed, after a proper suffix is closed, any future interval that reaches the earliest still-active vertex also reaches a later vertex that is already closed, thereby giving that closed vertex a second value-\(2\) neighbour.

The initial state is \((0,0,0,p_\infty,p_\infty)\) with value \(0\). A final state is accepting exactly when \(p=t=p_\infty\).

Processing a vertex of \(X\)

Suppose that \(x_i\) is processed from a finite state \((r_1,r_2,q,p,t)\).

1. If \(f(x_i)=0\), then \(x_i\) becomes active. If \(p=p_\infty\), the new active boundaries are \(p=t=i\). Otherwise, \(p\) remains unchanged and \(t\) becomes \(i\).

2. If \(f(x_i)=1\), then \(x_i\) is safe by itself. The state does not change, and the weight increases by \(1\).

3. If \(f(x_i)=2\), then \(x_i\) becomes the newest value-\(2\) vertex of \(X\). The new state is \((i,r_1,q,p,t)\), and the weight increases by \(2\).

Processing a vertex of \(Y\)

Let \(y\in Y_i\), and let \(l=l(y)\).

1. If \(f(y)=0\), then \(y\) must have exactly one value-\(2\) neighbour in \(N(y)=\{x_l,\ldots,x_i\}\). Since \(r_1\) and \(r_2\) are the rightmost and second rightmost value-\(2\) vertices of \(X\), this condition is equivalent to \(r_1\geq l\) and \(r_2<l\).

2. If \(f(y)=1\), then \(y\) is safe and does not affect any active or closed vertex of \(X\). The state is unchanged, and the weight increases by \(1\).

3. Suppose that \(f(y)=2\). First, \(y\) must avoid every closed vertex of \(X\). Since \(q\) is the largest closed index and \(N(y)\) is a suffix, this condition is exactly \(l>q\). If \(l\leq q\), the transition is infeasible. Assume that \(l>q\). If \(p=p_\infty\), then no active vertex exists, and the state is unchanged. If \(l\leq p\), then \(y\) reaches the earliest active vertex, and hence every active vertex; all active vertices become closed, the new closed boundary is \(t\), and the new state is \((r_1,r_2,t,p_\infty,p_\infty)\). If \(l>t\), then \(y\) reaches no active vertex and the state is unchanged. Finally, if \(p<l\leq t\), then \(y\) closes only a proper suffix of the active vertices, and the transition is discarded because it cannot be extended to a perfect Roman dominating function. In every feasible case, the weight increases by \(2\).

3.6 unique response Roman Domination↩︎

A unique response Roman dominating function of \(G\) is a Roman dominating function \(f:V(G)\rightarrow\{0,1,2\}\) satisfying the additional conditions that every vertex assigned value \(0\) has exactly one neighbour assigned value \(2\), and every vertex assigned value \(1\) or \(2\) has no neighbour assigned value \(2\). The unique response Roman domination number is denoted by \(u_R(G)\).

State.

The state is again a tuple \((r_1,r_2,q,p,t)\). The coordinates \(r_1\) and \(r_2\) are the largest and second largest indices of processed vertices of \(X\) assigned value \(2\). The coordinates \(p\) and \(t\) are the first and last active vertices of \(X\), where active means assigned value \(0\) but not yet dominated by a value-\(2\) vertex of \(Y\).

The meaning of \(q\) is stronger than in perfect Roman domination. A processed vertex of \(X\) is called forbidden if it is assigned value \(1\) or \(2\), or if it is assigned value \(0\) and is already closed. A future vertex of \(Y\) assigned value \(2\) must avoid every forbidden vertex. The coordinate \(q\) is the largest index of a forbidden vertex, and \(q=0\) if no forbidden vertex exists.

The initial state is \((0,0,0,p_\infty,p_\infty)\) with value \(0\). A final state is accepting exactly when \(p=t=p_\infty\).

Processing a vertex of \(X\)

Suppose that \(x_i\) is processed from a finite state \((r_1,r_2,q,p,t)\).

1. If \(f(x_i)=0\), then \(x_i\) becomes active. If \(p=p_\infty\), the new active boundaries are \(p=t=i\); otherwise, \(p\) remains unchanged and \(t\) becomes \(i\).

2. If \(f(x_i)=1\), then \(x_i\) becomes forbidden. This transition is feasible only when \(p=p_\infty\). Otherwise, any future value-\(2\) vertex of \(Y\) that reaches the earliest active vertex also reaches \(x_i\), contradicting the unique response condition. When the transition is feasible, the new state is \((r_1,r_2,i,p_\infty,p_\infty)\), and the weight increases by \(1\).

3. If \(f(x_i)=2\), then \(x_i\) becomes forbidden and also becomes the newest value-\(2\) vertex of \(X\). This transition is likewise feasible only when \(p=p_\infty\). The new state is \((i,r_1,i,p_\infty,p_\infty)\), and the weight increases by \(2\).

Processing a vertex of \(Y\)

Let \(y\in Y_i\), and let \(l=l(y)\).

1. If \(f(y)=0\), then \(y\) must have exactly one value-\(2\) neighbour in \(N(y)\). This is equivalent to \(r_1\geq l\) and \(r_2<l\).

2. If \(f(y)=1\), then \(y\) must have no value-\(2\) neighbour. Since \(r_1\) is the rightmost value-\(2\) vertex of \(X\), this condition is equivalent to \(r_1<l\). When it holds, the state is unchanged and the weight increases by \(1\).

3. Suppose that \(f(y)=2\). The vertex \(y\) must avoid all forbidden vertices of \(X\), which is equivalent to \(l>q\). If \(l\leq q\), the transition is infeasible. Assume that \(l>q\). If \(p=p_\infty\), then no active vertex exists and the state is unchanged. If \(l\leq p\), then \(y\) reaches and closes every active vertex; these vertices become forbidden, the new forbidden boundary is \(t\), and the new state is \((r_1,r_2,t,p_\infty,p_\infty)\). If \(l>t\), then \(y\) reaches no active vertex and the state remains unchanged. If \(p<l\leq t\), then \(y\) closes only a proper suffix of the active vertices, and the transition is discarded because any future value-\(2\) vertex needed to close the earliest active vertex would also reach a later forbidden vertex. In each feasible case, the weight increases by \(2\).

3.7 Pseudocode↩︎

We divide the unified framework into three parts. Algorithm 1 is the main routine, Algorithm 2 processes a vertex of \(X\), and Algorithm 3 processes a vertex of \(Y\). The parameter \(\Pi\) specifies the problem: \(\mathrm{R2}\), \(\mathrm{DR}\), \(\mathrm{PR}\), or \(\mathrm{UR}\).

A state is called finite if its table entry is smaller than \(+\infty\). In either transition subroutine, the temporary table \(D'\) is initialized with \(+\infty\) in every entry. Whenever several transitions produce the same state, the update convention keeps only the minimum resulting weight. The accepting states have deficit coordinates \((p_\infty,p_\infty)\) for \(\mathrm{R2}\) and \(\mathrm{DR}\), and active-boundary coordinates \((p_\infty,p_\infty)\) for \(\mathrm{PR}\) and \(\mathrm{UR}\).

3.8 Correctness Proof↩︎

We prove the four algorithms simultaneously through a common invariant. For each \(i\in\{1,\ldots,m\}\), let \(X_i=\{x_1,\ldots,x_i\}\) and \(Y_{\leq i}=\{y\in Y:r(y)\leq i\}\).

3.9 Running Time Analysis↩︎

3.10 Example↩︎

We illustrate the four variants on the same convex bipartite graph. Let \(X=\{x_1,x_2,x_3,x_4\}\) with ordering \(x_1,x_2,x_3,x_4\), and let \(Y=\{y_1,y_2,y_3\}\). Define \(N(y_1)=\{x_1,x_2,x_3\}\), \(N(y_2)=\{x_2,x_3,x_4\}\), and \(N(y_3)=\{x_3,x_4\}\). Then \(r(y_1)=3\), \(r(y_2)=4\), and \(r(y_3)=4\). Hence \(Y_1=Y_2=\emptyset\), \(Y_3=\{y_1\}\), and \(Y_4=\{y_2,y_3\}\), and the processing order is \(x_1,x_2,x_3,y_1,x_4,y_2,y_3\).

For Roman-\(\{2\}\) domination, assign value \(2\) to \(y_1\) and \(x_4\), and value \(0\) to every other vertex. Each of \(x_1,x_2,x_3\) receives total neighbour value \(2\) from \(y_1\), while \(y_2\) and \(y_3\) receive total neighbour value \(2\) from \(x_4\). Hence, the assignment is feasible and has weight \(4\). A direct examination of assignments of weight at most \(3\) shows that none can simultaneously provide total neighbour value at least \(2\) to the vertices at both ends of the convex ordering. Therefore \(\gamma_{\{R2\}}(G)=4\).

For double Roman domination, assign value \(3\) to \(y_1\) and \(x_4\), and value \(0\) to every other vertex. The vertices \(x_1,x_2,x_3\) are defended by \(y_1\), while \(y_2\) and \(y_3\) are defended by \(x_4\). Thus, the weight is \(6\). Since \(x_1\) has the unique neighbour \(y_1\), either \(x_1\) is positive or \(y_1\) has value \(3\). The analogous requirements near \(x_4\), together with the conditions for \(y_2\) and \(y_3\), force total weight at least \(6\). Hence \(\gamma_{dR}(G)=6\).

For perfect Roman domination, the assignment with \(f(y_1)=2\), \(f(x_4)=2\), and all other values equal to \(0\) is feasible. Each of \(x_1,x_2,x_3\) has exactly one value-\(2\) neighbour, namely \(y_1\), while each of \(y_2,y_3\) has exactly one value-\(2\) neighbour, namely \(x_4\). Since every perfect Roman dominating function is also a Roman dominating function and the ordinary Roman domination number of this graph is \(4\), the optimum is \(\gamma_R^p(G)=4\).

Finally, the same assignment is a unique response Roman dominating function. Every zero vertex has exactly one value-\(2\) neighbour, and the two value-\(2\) vertices \(y_1\) and \(x_4\) are nonadjacent. Therefore, no positive vertex has a value-\(2\) neighbour. Again, every unique response Roman dominating function is a Roman dominating function, so no solution of weight below \(4\) exists. Hence \(u_R(G)=4\).

4 Hardness of Roman-Type Domination Problems on Chordal Bipartite Graphs↩︎

In this section, we prove hardness results for several Roman-type domination problems on chordal bipartite graphs. We first prove NP-completeness for Roman-\(\{2\}\) domination by reducing from Dominating Set on chordal bipartite graphs. We then prove NP-completeness for unique response Roman domination by reducing from Efficient Domination on chordal bipartite graphs. Finally, we prove NP-completeness for perfect Roman domination by using a separate edge gadget that charges one extra unit whenever both endpoints of an original edge are selected. The Roman-\(\{2\}\) reduction uses one pendant vertex per original vertex, while the unique response Roman reduction uses two pendant vertices per original vertex.

4.1 Roman-\(\{2\}\) Domination↩︎

4.2 unique response Roman Domination↩︎

4.3 Perfect Roman Domination↩︎

The remaining variant is Perfect Roman domination. The two-pendant construction used for unique response Roman domination is not sufficient here, because in a perfect Roman dominating function, two adjacent vertices are allowed to both receive value \(2\). Therefore, we add an edge gadget that charges one extra unit whenever both endpoints of an original edge are selected. This restores the independence condition needed to simulate efficient domination.

5 Conclusion↩︎

In this paper, we studied four Roman-type domination problems on two important subclasses of bipartite graphs. For convex bipartite graphs, we developed a unified dynamic programming framework for Roman-\(\{2\}\) domination, double Roman domination, perfect Roman domination, and unique response Roman domination. The algorithms exploit a convex ordering of one bipartition class and process the graph from left to right. The main structural idea is that, after each processing step, the unfinished requirements of the processed vertices can be represented by a constant number of boundary indices. This compact representation yields \(O(n^6)\)-time algorithms for all four parameters.

We also established hardness results for chordal bipartite graphs. In particular, we proved that Roman-\(\{2\}\) domination, perfect Roman domination, and unique response Roman domination are NP-complete on this graph class. These results show that excluding induced cycles of length at least six is not sufficient to make these Roman-type domination problems tractable. Consequently, our results reveal a clear algorithmic contrast between convex bipartite graphs, where the interval structure supports polynomial-time dynamic programming, and the broader class of chordal bipartite graphs, where several of the corresponding problems remain computationally hard.

Several questions remain open. First, it would be interesting to improve the \(O(n^6)\) running times of the convex-bipartite algorithms, possibly by reducing the number of state coordinates, eliminating unreachable or equivalent states, or exploiting additional monotonicity in the dynamic programming tables. Since biconvex bipartite graphs and bipartite permutation graphs are subclasses of convex bipartite graphs, the algorithms presented in this paper already apply to them. Nevertheless, their stronger ordering properties may permit substantially faster algorithms.

Second, the complexity of these Roman-type domination problems deserves further investigation on graph classes that properly extend, or are not contained in, the class of convex bipartite graphs, such as circular-convex bipartite graphs, triad-convex bipartite graphs, and other restricted subclasses of tree-convex bipartite graphs. More generally, the results suggest the broader problem of identifying the precise structural boundary between bipartite graph classes on which Roman-type domination problems are polynomial-time solvable and those on which they remain NP-complete.

References↩︎

---

1. gkd@iitg.ac.in↩︎

2. kamal.7.2013@gmail.com, kamal.santra@iitg.ac.in↩︎