Algorithms and Logic Group

Sk Samim Islam: Multipacking in Graphs: Hardness Results and Approximation Algorithms on Graph Subclasses

Speaker:

Sk Samim Islam (Indian Statistical Institute, Kolkata, India)

Time:

  • 16:30-17:20 Beijing Time
  • December 12, 2025 (Friday)

Venue:

Join Zoom Meeting
https://us06web.zoom.us/j/87293332992?pwd=RwexmgEeYOaHpBaprbdO4P7FKC7KRV.1

Meeting ID: 872 9333 2992
Passcode: 009710

Abstract:

This talk focuses on the multipacking problem in undirected graphs. We begin by outlining the hardness results established for this problem. 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 every integer $r \ge 1$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$; equivalently, there are at most $r$ vertices of $M$ within distance $r$ from $v$ in $G$. The \emph{multipacking number} of $G$ is the maximum cardinality of a multipacking of $G$. The \textsc{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 \textsc{Multipacking} problem is \textsc{NP-complete} or solvable in polynomial time, although the problem is known to be polynomial-time solvable for certain graph classes (such as strongly chordal graphs, grids, etc.). We resolve this open question by proving that the \textsc{Multipacking} problem is \textsc{NP-complete} for undirected graphs. Moreover, we show that the problem is \textsc{W[2]-hard} when parameterized by the solution size. We further strengthen these results by proving that the problem remains \textsc{NP-complete} and \textsc{W[2]-hard} (under the same parameterization) even for several graph subclasses. Additionally, we design an exact exponential-time algorithm that computes a maximum multipacking in an $n$-vertex graph in time $O^*(1.63^n)$.

Finally, we present an approximation algorithm for the \textsc{Multipacking} problem on cactus graph. The talk will outline the proof technique behind the $1.5$-approximation algorithm for cactus graphs.

Speaker Bio:

Sk Samim Islam, Ph.D. scholar at the Indian Statistical Institute, Kolkata, India. 

,