Multipacking on graphs and Euclidean metric space

A \emph{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\ge 1$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$. The $\text{textsc}Multipacking$ problem asks whether a graph contains a multipacking of size at least $k$. For more than a decade, it remained open whether $\text{textsc}Multipacking$ is $\text{textsc}NP-complete$ or polynomial-time solvable, although it is known to be polynomial-time solvable for some classes (e.g., strongly chordal graphs and grids). Foucaud, Gras, Perez, and Sikora [$\mathit{\text{Algorithmica}}$ 2021] showed it is $\text{textsc}NP-complete$ for directed graphs and $\text{textsc}W[1]-hard$ when parameterized by the solution size. We resolve the open question by proving $\text{textsc}Multipacking$ is $\text{textsc}NP-complete$ for undirected graphs and $\text{textsc}W[2]-hard$ when parameterized by the solution size. Furthermore, we show it remains $\text{textsc}NP-complete$ and $\text{textsc}W[2]-hard$ even for chordal, bipartite, claw-free, regular, CONV, and chordal$\cap \frac{1}{2}$-hyperbolic graphs (a superclass of strongly chordal graphs), and we provide approximation algorithms for cactus, chordal, and $\delta$-hyperbolic graphs. Moreover, we study the relationship between multipacking number and broadcast domination number for cactus, chordal, and $\delta$-hyperbolic graphs. Further, we prove that for all $r\ge 2$, \textsc{$r$-Multipacking} is $\text{textsc}NP-complete$ even for planar bipartite graphs with bounded degree, and also for bounded-diameter chordal and bounded-diameter bipartite graphs. For geometric variants, in ${\mathbb{R}}^2$ a maximum $1$-multipacking can be computed in polynomial time, but computing a maximum $2$-multipacking is $\text{textsc}NP-hard$, and we provide approximation and parameterized algorithms for the $2$-multipacking problem.