On the Complexity of Signed Domination

Abstract

Given a graph $G=(V,E)$, a signed dominating function is a function $f:V\to \{-1,1\}$ such that for every vertex $u\in V$, $\sum _{v\in N[u]}f(v)\ge 1$. The weight of $f$ is defined as $\sum _{u\in V}f(u)$. The objective of the \sd{} problem is to compute a signed dominating function $f$ of minimum weight. The problem is known to be NP-complete even when restricted to bipartite, chordal, and planar graphs. In this paper, we extend the known complexity results for the \sd{} problem. Since the problem is NP-complete on chordal graphs, we study its complexity on split graphs, a subclass of chordal graphs, and show that it remains NP-complete. Moreover, as the problem is W[2]-hard parameterized by weight, we investigate its parameterized complexity with respect to structural parameters. We prove that the problem is W[1]-hard when parameterized by feedback vertex set number (and hence by treewidth and clique-width). Motivated by this hardness result, we consider more restrictive parameters, neighbourhood diversity and twin cover number, and present FPT algorithms.

Extended abstract of this paper has appeared in IWOCA 2026