On the Complexity of Multipacking

A multipacking in an undirected graph G = (V, E) is a set M ⊆ V such that for every vertex v ∈ V and for every integer r ≥ 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, although 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 [Foucaud et al., 2021] [Algorithmica 2021] made a step towards solving the open question by showing that the Multipacking problem is NP-complete for directed graphs and W[1]-hard when parameterized by the solution size. In this paper, we prove that the Multipacking problem is NP-complete on undirected graphs, which answers the open question. Moreover, the problem is W[2]-hard on undirected graphs when parameterized by the solution size. Furthermore, we show that the problem is NP-complete and W[2]-hard (parameterized by solution size) on chordal, bipartite, and claw-free graphs, and remains NP-complete on regular and CONV graphs (intersection graphs of convex sets in the plane). Additionally, the problem is NP-complete and W[2]-hard (parameterized by the solution size) on chordal ∩ 1/2-hyperbolic graphs, which is a superclass of strongly chordal graphs on which the problem is polynomial-time solvable. On the positive side, we present an exact exponential-time algorithm for the Multipacking problem on general graphs that breaks the 2ⁿ barrier, with running time O^*(1.58ⁿ), where n is the number of vertices.