Multipacking on graphs and Euclidean metric space
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917257546825728 |
|---|---|
| author | Islam, Sk Samim |
| author_facet | Islam, Sk Samim |
| contents | 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\geq 1$, the ball of radius $ r $ around $ v $ contains at most $r$ vertices of $M$. The \textsc{Multipacking} problem asks whether a graph contains a multipacking of size at least $k$. For more than a decade, it remained open whether \textsc{Multipacking} is \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 [\textit{Algorithmica} 2021] showed it is \textsc{NP-complete} for directed graphs and \textsc{W[1]-hard} when parameterized by the solution size. We resolve the open question by proving \textsc{Multipacking} is \textsc{NP-complete} for undirected graphs and \textsc{W[2]-hard} when parameterized by the solution size. Furthermore, we show it remains \textsc{NP-complete} and \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 $δ$-hyperbolic graphs. Moreover, we study the relationship between multipacking number and broadcast domination number for cactus, chordal, and $δ$-hyperbolic graphs. Further, we prove that for all $r\geq 2$, \textsc{$r$-Multipacking} is \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 \textsc{NP-hard}, and we provide approximation and parameterized algorithms for the $2$-multipacking problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07927 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Multipacking on graphs and Euclidean metric space Islam, Sk Samim Discrete Mathematics 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\geq 1$, the ball of radius $ r $ around $ v $ contains at most $r$ vertices of $M$. The \textsc{Multipacking} problem asks whether a graph contains a multipacking of size at least $k$. For more than a decade, it remained open whether \textsc{Multipacking} is \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 [\textit{Algorithmica} 2021] showed it is \textsc{NP-complete} for directed graphs and \textsc{W[1]-hard} when parameterized by the solution size. We resolve the open question by proving \textsc{Multipacking} is \textsc{NP-complete} for undirected graphs and \textsc{W[2]-hard} when parameterized by the solution size. Furthermore, we show it remains \textsc{NP-complete} and \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 $δ$-hyperbolic graphs. Moreover, we study the relationship between multipacking number and broadcast domination number for cactus, chordal, and $δ$-hyperbolic graphs. Further, we prove that for all $r\geq 2$, \textsc{$r$-Multipacking} is \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 \textsc{NP-hard}, and we provide approximation and parameterized algorithms for the $2$-multipacking problem. |
| title | Multipacking on graphs and Euclidean metric space |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2602.07927 |