Sk Samim Islam

dblp:339/2128 · DBLP profile ↗
← Back
4ranked-venue papers
0as first author
4since 2021 · last 2026
0009-0007-8974-5920ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 since 2021Graphics, computer vision, multimedia, augmented reality and games · 1 · 1 since 2021
YearPublicationVenuePosition
2026 On the Complexity of Multipacking
abstract
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.
Sandip Das 0001, Sk Samim Islam, Daniel Lokshtanov
ESA2
2026 Growth rates of the number of empty triangles and simplices
Bhaswar B. Bhattacharya, Sandip Das 0001, Sk Samim Islam, Saumya Sen
Comput. Geom.3
2026 Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs
Sandip Das 0001, Florent Foucaud, Sk Samim Islam, Joydeep Mukherjee
Discret. Appl. Math.3
2025 On Distance-d Independent Set Problems for Some Graph Classes
Sandip Das 0001, Soura Sena Das, Sweta Das, Sk Samim Islam
FCT4