{"ID":2834324,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.02083","arxiv_id":"2512.02083","title":"On the Complexity of Signed Roman Domination","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2512.02083","url_pdf":"https://arxiv.org/pdf/2512.02083v1","authors":"[\"Sangam Balchandar Reddy\"]","published":"2025-12-01T05:46:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}