Sahiba

dblp:413/7070 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
0009-0009-7271-2406ORCID · reported

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

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 The Parameterized Complexity of Maximum Span on Natural Matroid Classes
abstract
We study Maximum Span, motivated by the recent Maximum Span Hypothesis of Karthik and Khot [SODA 2025], which suggests strong parameterized intractability for finding large structured subsets in vector spaces. Formally, given a matrix M and integers k and t, the task is to decide whether there exists a linearly independent set S of at most k columns such that at least t additional columns of M lie in span(S). Equivalently, the goal is to identify a low-rank witness whose span covers many input columns. We initiate a systematic study of the parameterized complexity of Maximum Span on natural matroid classes, revealing a diverse complexity landscape. We first show that the problem is polynomial-time solvable on laminar matroids, via a dynamic program over the laminar tree. In sharp contrast, on graphic matroids the problem is W[1]-hard parameterized by k+t, and, assuming Gap-ETH, admits no f(k)⋅ n^𝒪(1)-time k^o(1)-approximation. On cographic matroids, we show that the problem is equivalent to deleting at most k+t edges so as to create at least t+1 connected components; this yields fixed-parameter tractability parameterized by k+t, and W[1]-hardness parameterized by t. On transversal matroids, using a Hall-type interpretation, we prove W[1]-hardness parameterized by k+t. For strict gammoids, we develop a separator-based formulation. We prove W[1]-hardness parameterized by k+t, give an XP algorithm parameterized by t, and obtain FPT 2^k-approximation algorithms in both the directed and undirected settings. For general gammoids, we establish W[1]-hardness parameterized by k+t, NP-hardness already for t = 1, and an XP algorithm parameterized by k. Together, these results give a detailed parameterized complexity map for Maximum Span across fundamental matroid classes, ranging from polynomial-time solvability to fixed-parameter algorithms, XP algorithms, approximation algorithms, and strong hardness.
Madhumita Kundu, Ashutosh Rai 0001, Sahiba, Saket Saurabh 0001
MFCS3
2025 Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components
Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, Saket Saurabh 0001
MFCS5