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.

翻译：给定图 $G = (V, E)$，符号罗马支配函数是一个函数 $f: V \\rightarrow \\{-1, 1, 2\\}$，满足对于每个顶点 $u \\in V$：$\\sum_{v \\in N[u]} f(v) \\geq 1$，且对于每个满足 $f(u) = -1$ 的顶点 $u \\in V$，存在一个顶点 $v \\in N(u)$ 使得 $f(v) = 2$。符号罗马支配函数 $f$ 的权重定义为 $\\sum_{u \\in V} f(u)$。\\srd{}（SRD）问题的目标是计算具有最小权重的符号罗马支配函数。已知该问题即使在二分图和平面图上也是 NP 完全的。本文通过证明该问题在分裂图上仍保持 NP 完全性，推进了复杂性研究。在参数化复杂性领域，我们证明了该问题在权重参数化下是 W[2]-难的，即使在二分图上也是如此。我们进一步证明，该问题在反馈顶点集数参数化下是 W[1]-难的（因此在树宽或团宽参数化下也是 W[1]-难的）。在积极方面，我们提出了一个在邻域多样性（以及顶点覆盖数）参数化下的 FPT 算法。最后，我们通过证明除非 coNP $\\subseteq$ NP/poly，否则该问题在顶点覆盖数参数化下不存在多项式核，从而补充了这一结果。