EDBT 2026 Demo / reviewers in the wild / expert
Sk Samim Islam
dblp:339/2128
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2026 | On the Complexity of MultipackingabstractA 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 |
ESA | 2 |
| 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 |
FCT | 4 |