{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreicy7vcnh7hdz4twlf5ewze4g4im2za4qrtrmmhiylamdhr7hqql5m",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mlnlxskurls2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.10607v1",
  "publishedAt": "2026-05-12T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Christoph Grüne",
    "Tom Janßen"
  ],
  "textContent": "**Authors:** Christoph Grüne, Tom Janßen\n\nThe problem Defensive $δ$-Covering, for some covering range $δ> 0$, is a continuous facility location problem on undirected graphs where all edges have unit length. It is a generalization of Defensive Dominating Set and $δ$-Covering. An attack and defense are sets of points, which are on vertices or on the interior of an edge. A defense counters an attack, if there is a matching of the points in the defense to the points in the attack, such that any matched points have distance at most $δ$, and every point in the attack is matched. The task is, given a graph $G$ and numbers $\\ell, k \\in \\mathbb N$, to find a defense of size at most $\\ell$ that counters every possible attack of size at most $k$. We study the complexity of this problem in various different settings. We show that if the attack is restricted to vertices, the problem is $Σ^P_2$-complete for large $δ$, but if the attack may consist of any points on the graph, it is NP-complete. Additionally, we analyze how the complexity changes if the attacks or defenses may be a multiset. If the defense is allowed to be a multiset, the complexity does not change in any case we consider, while if the attack is allowed to be a multiset, the problem often becomes easier. To show containment in the various complexity classes, we introduce a number of discretization arguments, which show that solutions with a regular structure must always exist.",
  "title": "Continuous Defensive Domination Problems"
}