2026-08-25T18:47:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27288 2026-08-25T13:18:21Z ddc:004 open_access

On the Complexity of Multipacking Das, Sandip Islam, Sk Samim Lokshtanov, Daniel Multipacking Complexity Exact exponential algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sandip Das and Sk Samim Islam and Daniel Lokshtanov 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.152 urn:nbn:de:0030-drops-272885 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.152 eng https://creativecommons.org/licenses/by/4.0/legalcode