On the Complexity of Signed Roman Domination Journal: Theoretical Computer Science

Sangam Balchandar Reddy · 2025

Read On the Complexity of Signed Roman Domination Journal: Theoretical Computer Science by Sangam Balchandar Reddy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-02083.txt.

Introduction

Domination problems ask how to place guards on a network so every node is covered, and the Roman variant lets some posts count double. Sangam Balchandar Reddy analyzes in 2025 the computational complexity of signed Roman domination, where vertices receive values that can also be negative.

A signed Roman dominating function must give every closed neighborhood a positive total weight while obeying rules at each vertex. Knowing whether finding the best such assignment is easy or provably hard guides algorithm designers. Complexity results like this sort network optimization problems into those worth attacking exactly and those needing heuristics.

Catalog record

CREATORSangam Balchandar Reddy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-02083

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Complexity of Signed Roman Domination Journal: Theoretical Computer Science Sangam Balchandar Reddy Abstract Given a graph G = ( V , E ) G=(V,E) , a signed Roman dominating function is a function f : V → { − 1 , 1 , 2 } f:V\rightarrow\{-1,1,2\} such that for every vertex u ∈ V u\in V : ∑ v ∈ N ⁡ [ u ] f ⁡ ( v ) ≥ 1 \sum_{v\in N[u]}f(v)\geq 1 and for every vertex u ∈ V u\in V with f ⁡ ( u ) = − 1 f(u)=-1 , there exists a vertex v ∈ N ⁡ ( u ) v\in N(u) with f ⁡ ( v ) = 2 f(v)=2 . The weight of a signed Roman dominating function f f is ∑ u ∈ V f ⁡ ( u ) \sum_{u\in V}f(u) . The objective of Signed Roman Domination (SRD) problem is to compute a signed Roman dominating function with minimum weight. The problem is known to be NP-complete even when restricted to bipartite graphs and planar graphs. In this paper, we advance the complexity study by showing that the problem remains NP-complete on split graphs. In the realm of parameterized complexity, we prove that the problem is W[2]-hard parameterized by weight, even on bipartite graphs. We further show that the problem is W[1]-hard parameterized by feedback vertex set number (and hence also when parameterized by treewidth or clique-width). On the positive side, we present an FPT algorithm parameterized by neighbourhood diversity (and by vertex cover number). Finally, we complement this result by proving that the problem does not admit a polynomial kernel parameterized by vertex cover number unless coNP ⊆ \subseteq NP/poly. 1 Introduction Dominating Set (DS) problem is one of the first few problems that were proved to be NP-complete [ 1 ] in 1972. Given a graph G=(V,E) , a set S\subseteq V is a dominating set if for each vertex u\in V , |N[u]\cap S|\geq 1 . The objective of DS problem is to compute a minimum sized dominating set. Since the inception of DS problem, many variants have been introduced. One such variant is the Roman Domination (RD) problem. The concept of RD problem draws inspiration from the strategic positioning of legions to protect the Roman Empire. The RD problem was introduced by Cockayne et al. [ 2 ] in 2004. Given a graph G=(V,E) , a Roman dominating function f:V\rightarrow{}\{0,1,2\} is a labeling of vertices such that for each vertex u\in V with f(u)=0 , there exists a vertex v\in N(u) with f(v)=2 . The goal of RD problem is to obtain a Roman dominating function f with minimum weight. We now define another variant of DS problem, namely, the Signed Domination problem (SD). A function f:V\rightarrow{}\{-1,1\} is a signed dominating function, if \sum_{v\in N[u]}f(v)\geq 1 , for every u\in V . The objective of SD problem is to compute a signed dominating function f with minimum weight. Various versions of RD problem such as Double Roman Domination [ 3 ] , Global Roman Domination [ 4 ] , Edge Roman Domination [ 5 ] , Weak Roman Domination [ 6 , 7 ] and Total Roman Domination [ 8 ] were studied from an algorithmic standpoint. In this work, we consider a relatively new variant, namely the Signed Roman Domination problem. The concept of SRD problem was introduced by Ahangar et al. [ 9 ] in 2014. A signed Roman dominating function on a graph G is a function f:V\rightarrow\{-1,1,2\} such that for each u\in V : \sum_{v\in N[u]}f(v)\geq 1 , and every vertex u for which f(u)=-1 is adjacent to a vertex v with f(v)=2 . The weight of a signed Roman dominating function f is \sum_{u\in V}f(u) . The minimum weight over all signed Roman dominating functions for G is denoted by \gamma_{sR}(G) . The objective of SRD problem is to compute \gamma_{sR}(G) . We formally define the problem as follows. Signed Roman Domination : Input: An instance I = (G,k) , where G=(V,E) is an undirected graph and an integer k . Output: Yes, if there exists a function f:V\rightarrow{}\{-1,1,2\} such that (1) \sum_{u\in V}f(u)\leq k , (2) \sum_{v\in N[u]}f(v)\geq 1 for each vertex u\in V and (3) there exists a vertex v\in N(u) such that f(v)=2 for each vertex u with f(u)=-1 ; No, otherwise. Known results. SRD problem was shown to be NP-complete even when restricted to bipartite graphs and planar graphs [ 10 ] . There exist methods to obtain \gamma_{sR}(G) in cycles and fan graphs [ 11 ] . Hong et al. [ 12 ] determined \gamma_{sR}(G) for spider graphs and double star graphs. Yancai et al. [ 13 ] obtained the value of \gamma_{sR}(G) for complete bipartite graphs and wheels. Ahangar et al. [ 9 ] provided several upper and lower bounds on bipartite and general graphs in terms of its order, size and vertex degrees. For instance, they have shown that for a graph G with n vertices, \displaystyle\gamma_{sR}(G)\geq\left(\frac{-2\Delta^{2}+2\Delta\delta+\Delta+2\delta+3}{(\Delta+1)(2\Delta+\delta+3)}\right)n, where \Delta and \delta indicate the maximum degree and minimum degree of the graph G , respectively. There are several combinatorial bounds obtained for the problem on digraphs [ 14 ] and a class of planar graphs called convex polytopes [ 15 ] . The DS problem has been extensively studied in the realm of parameterized complexity. Raman et al. [ 16 ] proved that DS problem is W[2]-complete for split graphs and bipartite graphs. There exists an \mathcal{O}^{*}(3^{tw}) -time FPT algorithm for DS problem where tw denotes the treewidth [ 17 ] . The parameterized complexity of RD problem has been initiated by Fernau et al. [ 18 ] . They showed that RD problem is known to be W[2]-complete for general graphs. They have also presented FPT algorithms for graphs of bounded treewidth and planar graphs. Zheng et al. [ 19 ] studied the kernelization aspects of Signed Domination on general graphs, planar graphs, d -partite graphs, bounded degree graphs, r -regular graphs and grid graphs. Zheng et al. [ 20 ] initiated the parameterized complexity of SD problem. They showed that the problem is FPT parameterized by treewidth. They also presented kernels for bipartite graphs, bounded degree graphs, regular graphs and planar graphs. Later, Lin et al. [ 21 ] proved that the problem is W[2]-hard parameterized by weight. They also presented an FPT algorithm for subcubic graphs. Our results. The primary motivation to study the complexity of SRD problem is due to its ability to combine the properties of both RD problem and SD problem. We attempted to analyze the complexity difference of SRD problem to that of RD problem and SD problem. In this regard, we were able to prove that SRD problem is W[1]-hard parameterized by treewidth whereas both RD problem and SD problem admit FPT algorithms, which is the key contribution of this work. We obtain the following results for SRD problem in the realm of classical and parameterized complexity. 1. The complexity of SRD problem on split graphs and chordal graphs is open. In this regard, we study the complexity of the problem on split graphs (a subclass of chordal graphs) and prove that the problem is

Read the complete text