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

Abstract

This talk focuses on the multipacking problem in undirected graphs. We begin by outlining the hardness results established for this problem. A 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 multipacking number of $G$ is the maximum cardinality of a multipacking of $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 (such as strongly chordal graphs, grids, etc.). We resolve this open question by proving that the Multipacking problem is NP-complete for undirected graphs. Moreover, we show that the problem is W[2]-hard when parameterized by the solution size. We further strengthen these results by proving that the problem remains NP-complete and 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 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.

Online Access

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

Meeting ID: 872 9333 2992
Passcode: 009710