Diptapriyo Majumdar
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Diptapriyo Majumdar has a total of 48 co-authors. Here are the top co-authors by number of shared publications:
Venkatesh Raman
9 shared publications- Venkatesh Raman
The Institute of Mathematical Sciences HBNI Chennai India
6 shared publications Ashwin Jacob
4 shared publications- Eduard Eiben
Royal Holloway, University of London
4 shared publications - Maadapuzhi-Sridharan Ramanujan
University of Warwick, Coventry, United Kingdom
4 shared publications - Ashwin Jacob
Department of Computer Science & Engineering, National Institute of Technology Calicut, Kerala 673601, India
3 shared publications
Latest Publications
- 10 September 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1502-1541
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
We investigate fine-grained algorithmic aspects for classical identification problems in graphs, namely, Locating-Dominating Set, and in set systems, namely, Test Cover. In the first problem, an input is a graph [Formula: see text] on [Formula: see text] vertices and an integer [Formula: see text], and the objective is to decide whether there is a subset [Formula: see text] of [Formula: see text] vertices such that any two distinct vertices not in [Formula: see text] are dominated by distinct subsets of [Formula: see text]. In the second problem, an input is a set [Formula: see text] of items, a collection [Formula: see text] of subsets of [Formula: see text] called tests, and an integer [Formula: see text], and the objective is to select a set [Formula: see text] of at most [Formula: see text] tests such that any two distinct items are contained in a distinct subset of tests of [Formula: see text]. For our first result, we Locating-Dominating Set (respectively, Test Cover) parameterized by the treewidth of the input graph (respectively, the incidence graph) does not admit an algorithm running in time [Formula: see text] (respectively, [Formula: see text]), unless the exponential-time hypothesis ( ETH) fails. Next, we prove that unless the ETH fails, Locating-Dominating Set does not admit an algorithm running in time [Formula: see text] or a polynomial-time kernelization algorithm that reduces the solution size and outputs a kernel with [Formula: see text] vertices, and Test Cover does not admit an algorithm running in time [Formula: see text] or a kernel with [Formula: see text] vertices. Again, we show that these lower bounds are tight by designing (kernelization) algorithms with matching running times.
- 10 September 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1502-1541
Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
We investigate fine-grained algorithmic aspects for classical identification problems in graphs, namely, Locating-Dominating Set, and in set systems, namely, Test Cover. In the first problem, an input is a graph [Formula: see text] on [Formula: see text] vertices and an integer [Formula: see text], and the objective is to decide whether there is a subset [Formula: see text] of [Formula: see text] vertices such that any two distinct vertices not in [Formula: see text] are dominated by distinct subsets of [Formula: see text]. In the second problem, an input is a set [Formula: see text] of items, a collection [Formula: see text] of subsets of [Formula: see text] called tests, and an integer [Formula: see text], and the objective is to select a set [Formula: see text] of at most [Formula: see text] tests such that any two distinct items are contained in a distinct subset of tests of [Formula: see text]. For our first result, we Locating-Dominating Set (respectively, Test Cover) parameterized by the treewidth of the input graph (respectively, the incidence graph) does not admit an algorithm running in time [Formula: see text] (respectively, [Formula: see text]), unless the exponential-time hypothesis ( ETH) fails. Next, we prove that unless the ETH fails, Locating-Dominating Set does not admit an algorithm running in time [Formula: see text] or a polynomial-time kernelization algorithm that reduces the solution size and outputs a kernel with [Formula: see text] vertices, and Test Cover does not admit an algorithm running in time [Formula: see text] or a kernel with [Formula: see text] vertices. Again, we show that these lower bounds are tight by designing (kernelization) algorithms with matching running times.
- 21 May 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 161
A polynomial kernel for deletion to the scattered class of cliques and trees
- 21 May 2026
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 161
A polynomial kernel for deletion to the scattered class of cliques and trees
- 6 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints
- 6 March 2026
- Published by Elsevier in Information and Computation
- Vol. 310
On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints
- 13 February 2026
- Published by Springer Nature
- p. 172-186
Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
- 13 February 2026
- Published by Springer Nature
- p. 172-186
Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree
- 6 February 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (1) , 102-133
Highly Connected Steiner Subgraph: Parameterized Algorithms and Applications to Hitting Set Problems
Given a simple (connected) undirected graph [Formula: see text], a set [Formula: see text] and integers [Formula: see text] and [Formula: see text], the Steiner Subgraph Extension problem asks whether there exists a set [Formula: see text] of at most [Formula: see text] vertices such that [Formula: see text] is a [Formula: see text]-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set [Formula: see text] and [Formula: see text] to be the terminals). In this paper, we initiate the study of Steiner Subgraph Extension from the perspective of parameterized complexity and give a fixed-parameter algorithm (i.e., FPT algorithm) parameterized by [Formula: see text] and [Formula: see text] on graphs of bounded degeneracy. In case we remove the assumption of the graph being bounded degenerate, then Steiner Subgraph Extension becomes W[1]-hard. Besides being an independent advance on the parameterized complexity of network design problems, our result has natural applications. In particular, we use our result to obtain new single-exponential FPT algorithms for several vertex-deletion problems studied in the literature, where the goal is to delete a smallest set of vertices such that (i) the resulting graph belongs to a specified hereditary graph class, and (ii) the deleted set of vertices induces a [Formula: see text]-edge-connected subgraph of the input graph.
- 6 February 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (1) , 102-133
Highly Connected Steiner Subgraph: Parameterized Algorithms and Applications to Hitting Set Problems
Given a simple (connected) undirected graph [Formula: see text], a set [Formula: see text] and integers [Formula: see text] and [Formula: see text], the Steiner Subgraph Extension problem asks whether there exists a set [Formula: see text] of at most [Formula: see text] vertices such that [Formula: see text] is a [Formula: see text]-edge-connected subgraph. This problem is a natural generalization of the well-studied Steiner Tree problem (set [Formula: see text] and [Formula: see text] to be the terminals). In this paper, we initiate the study of Steiner Subgraph Extension from the perspective of parameterized complexity and give a fixed-parameter algorithm (i.e., FPT algorithm) parameterized by [Formula: see text] and [Formula: see text] on graphs of bounded degeneracy. In case we remove the assumption of the graph being bounded degenerate, then Steiner Subgraph Extension becomes W[1]-hard. Besides being an independent advance on the parameterized complexity of network design problems, our result has natural applications. In particular, we use our result to obtain new single-exponential FPT algorithms for several vertex-deletion problems studied in the literature, where the goal is to delete a smallest set of vertices such that (i) the resulting graph belongs to a specified hereditary graph class, and (ii) the deleted set of vertices induces a [Formula: see text]-edge-connected subgraph of the input graph.
- 2 January 2026
- Published by Springer Nature
- p. 331-344
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
- 2 January 2026
- Published by Springer Nature
- p. 331-344
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
- Open Access
On the Structural Parameterizations of 2-Club with Triangle Constraints
Given an undirected graph G = (V, E) and an integer k, the s-Club asks if Gcontains a vertex subset S of at least k vertices such that G[S] has diameter at most s. Recently, Vertex r-Triangle s-Club, and Edge r-Triangle s-Club that generalize the notion of s-Club have been studied by Garvardt et al. [TOCS-2023, IWOCA-2022] from the perspective of parameterized complexity. Given a graph G and an integer k, the Vertex r-Triangle s-Club asks if there is an s-Club S with at least k vertices such that every vertex u \in S is part of at least r triangles in G[S]. In this paper, we initiate a systematic study of Vertex r-Triangle s-Club for every integer r >= 1 from the perspective of structural parameters of the input graph. In particular, we provide FPT algorithms for Vertex r-Triangle 2-Club when parameterized by the treewidth (tw) of the input graph, and an XP algorithm when parameterized by the h-index of the input graph. Additionally, when parameterized by the feedback edge number (fes) of the input graph. We provide a kernel of O(fes) edges for Vertex r-Triangle s-Club.
Open AccessOn the Structural Parameterizations of 2-Club with Triangle Constraints
Given an undirected graph G = (V, E) and an integer k, the s-Club asks if Gcontains a vertex subset S of at least k vertices such that G[S] has diameter at most s. Recently, Vertex r-Triangle s-Club, and Edge r-Triangle s-Club that generalize the notion of s-Club have been studied by Garvardt et al. [TOCS-2023, IWOCA-2022] from the perspective of parameterized complexity. Given a graph G and an integer k, the Vertex r-Triangle s-Club asks if there is an s-Club S with at least k vertices such that every vertex u \in S is part of at least r triangles in G[S]. In this paper, we initiate a systematic study of Vertex r-Triangle s-Club for every integer r >= 1 from the perspective of structural parameters of the input graph. In particular, we provide FPT algorithms for Vertex r-Triangle 2-Club when parameterized by the treewidth (tw) of the input graph, and an XP algorithm when parameterized by the h-index of the input graph. Additionally, when parameterized by the feedback edge number (fes) of the input graph. We provide a kernel of O(fes) edges for Vertex r-Triangle s-Club.
- 18 May 2025
- Published by Springer Nature
- p. 187-204
Structural Parameterization of Locating-Dominating Set and Test Cover
- 18 May 2025
- Published by Springer Nature
- p. 187-204
Structural Parameterization of Locating-Dominating Set and Test Cover
- 4 May 2025
- Published by Springer Nature
- p. 14-25
Parameterized Complexity of Shortest Path with Positive Disjunctive Constraints
- 4 May 2025
- Published by Springer Nature
- p. 14-25
Parameterized Complexity of Shortest Path with Positive Disjunctive Constraints
- Open Access
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
Enumeration kernelization for parameterized enumeration problems was defined by Creignou et al. [Theory Comput. Syst. 2017] and was later refined by Golovach et al. [J. Comput. Syst. Sci. 2022, STACS 2021] to polynomial-delay enumeration kernelization. We consider ENUM LONG-PATH, the enumeration variant of the Long-Path problem, from the perspective of enumeration kernelization. Formally, given an undirected graph G and an integer k, the objective of ENUM LONG-PATH is to enumerate all paths of G having exactly k vertices. We consider the structural parameters vertex cover number, dissociation number, and distance to clique and provide polynomial-delay enumeration kernels of polynomial size for each of these parameters.
Open AccessPolynomial-Size Enumeration Kernelizations for Long Path Enumeration
Enumeration kernelization for parameterized enumeration problems was defined by Creignou et al. [Theory Comput. Syst. 2017] and was later refined by Golovach et al. [J. Comput. Syst. Sci. 2022, STACS 2021] to polynomial-delay enumeration kernelization. We consider ENUM LONG-PATH, the enumeration variant of the Long-Path problem, from the perspective of enumeration kernelization. Formally, given an undirected graph G and an integer k, the objective of ENUM LONG-PATH is to enumerate all paths of G having exactly k vertices. We consider the structural parameters vertex cover number, dissociation number, and distance to clique and provide polynomial-delay enumeration kernels of polynomial size for each of these parameters.