{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifjepht2dga5csvzo2inaed3eh7piic2qpojzgrbn7sbxx3sovxu4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mekgfxopvxs2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.07982v1",
  "publishedAt": "2026-02-10T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sandip Das",
    "Sk Samim Islam",
    "Daniel Lokshtanov"
  ],
  "textContent": "**Authors:** Sandip Das, Sk Samim Islam, Daniel Lokshtanov\n\nA multipacking in an undirected graph $G=(V,E)$ is a set $M\\subseteq V$ such that for every vertex $v\\in V$ and for every integer $r\\geq 1$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$, that is, there are at most $r$ vertices in $M$ at a distance at most $r$ from $v$ in $G$. The Multipacking problem asks whether a graph contains a multipacking of size at least $k$. For more than a decade, it remained an open question whether the Multipacking problem is NP-complete or solvable in polynomial time. Whereas the problem is known to be polynomial-time solvable for certain graph classes (e.g., strongly chordal graphs, grids, etc). Foucaud, Gras, Perez, and Sikora [Algorithmica 2021] made a step towards solving the open question by showing that the Multipacking problem is NP-complete for directed graphs and it is W[1]-hard when parameterized by the solution size. In this paper, we prove that the Multipacking problem is NP-complete for undirected graphs, which answers the open question. Moreover, the problem is W[2]-hard for undirected graphs when parameterized by the solution size. Furthermore, we have shown that the problem is NP-complete and W[2]-hard (when parameterized by the solution size) even for various subclasses: chordal, bipartite, and claw-free graphs. Whereas, it is NP-complete for regular, and CONV graphs (intersection graphs of convex sets in the plane). Additionally, the problem is NP-complete and W[2]-hard (when parameterized by the solution size) for chordal $\\cap$ $\\frac{1}{2}$-hyperbolic graphs, which is a superclass of strongly chordal graphs where the problem is polynomial-time solvable. On the positive side, we present an exact exponential-time algorithm for the Multipacking problem on $n$-vertex general graphs, which breaks the $2^n$ barrier by achieving a running time of $O^*(1.58^n)$.",
  "title": "On the complexity of Multipacking"
}