On the Complexity of Signed Roman Domination
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909939604127744 |
|---|---|
| author | Reddy, Sangam Balchandar |
| author_facet | Reddy, Sangam Balchandar |
| contents | Given a graph $G = (V, E)$, a signed Roman dominating function is a function $f: V \rightarrow \{-1, 1, 2\}$ such that for every vertex $u \in V$: $\sum_{v \in N[u]} f(v) \geq 1$ and for every vertex $u \in V$ with $f(u) = -1$, there exists a vertex $v \in N(u)$ with $f(v) = 2$. The weight of a signed Roman dominating function $f$ is $\sum_{u \in V} f(u)$. The objective of \srd{} (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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_02083 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Signed Roman Domination Reddy, Sangam Balchandar Data Structures and Algorithms Computational Complexity Given a graph $G = (V, E)$, a signed Roman dominating function is a function $f: V \rightarrow \{-1, 1, 2\}$ such that for every vertex $u \in V$: $\sum_{v \in N[u]} f(v) \geq 1$ and for every vertex $u \in V$ with $f(u) = -1$, there exists a vertex $v \in N(u)$ with $f(v) = 2$. The weight of a signed Roman dominating function $f$ is $\sum_{u \in V} f(u)$. The objective of \srd{} (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. |
| title | On the Complexity of Signed Roman Domination |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2512.02083 |