{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicgulhrqopgnhoroo5j7fp6er4l7puewy7iddpuhzr6cqx3mg7sea",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnwgvfbvv7i2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.10670v1",
  "publishedAt": "2026-06-10T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sangam Balchandar Reddy"
  ],
  "textContent": "**Authors:** Sangam Balchandar Reddy\n\nGiven a graph $G = (V, E)$, a signed dominating function is a function $f: V \\rightarrow \\\\{-1, 1\\\\}$ such that for every vertex $u \\in V$, $\\sum\\limits_{v \\in N[u]} f(v) \\geq 1$. The weight of $f$ is defined as $\\sum\\limits_{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.",
  "title": "On the Complexity of Signed Domination"
}