Search Results

Documents authored by Sahiba

Document
DOI: 10.4230/LIPIcs.MFCS.2026.95
The Parameterized Complexity of Maximum Span on Natural Matroid Classes

Authors: Madhumita Kundu, Ashutosh Rai, Sahiba, and Saket Saurabh

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

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.
Cite as

Madhumita Kundu, Ashutosh Rai, Sahiba, and Saket Saurabh. The Parameterized Complexity of Maximum Span on Natural Matroid Classes. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 95:1-95:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kundu_et_al:LIPIcs.MFCS.2026.95,
  author =	{Kundu, Madhumita and Rai, Ashutosh and Sahiba and Saurabh, Saket},
  title =	{{The Parameterized Complexity of Maximum Span on Natural Matroid Classes}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{95:1--95:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.95},
  URN =		{urn:nbn:de:0030-drops-274775},
  doi =		{10.4230/LIPIcs.MFCS.2026.95},
  annote =	{Keywords: Fixed Parameter Tractability, W\lbrack1\rbrack-hardness, FPT Approximation, Graphic Matroids, Cographic Matroids, Transversal Matroids, Strict Gammoids, Gammoids, Laminar Matroids}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.20
Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components

Authors: Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Motivated by the growing interest in graph clustering and the framework proposed during the Dagstuhl Seminar 23331, we consider a natural specialization of this general approach (as also suggested during the seminar). The seminar introduced a broad perspective on clustering, where the goal is to partition a graph into connected components (or "clusters") that satisfy simple structural integrity constraints - not necessarily limited to cliques. In our work, we focus on the case where each cluster is required to have bounded vertex cover number. Specifically, a connected component C satisfies this condition if there exists a set S ⊆ V(C) with |S| ≤ d such that C - S is an independent set. We study this within the framework of the {Vertex Deletion to d-Vertex Cover Components} ({Vertex Deletion to d-VCC}) problem: given a graph G and an integer k, the task is to determine whether there exists a vertex set S ⊆ V(G) of size at most k such that every connected component of G - S has vertex cover number at most d. We also examine the edge-deletion variant, {Edge Deletion to d-Vertex Cover Components} ({Edge Deletion to d-VCC}), where the goal is to delete at most k edges so that each connected component of the resulting graph has vertex cover number at most d. We obtain following results. 1) {Vertex Deletion to d-VCC} admits a kernel with {𝒪}(d⁶k³) vertices and {𝒪}(d⁹k⁴) edges. 2) {Edge Deletion to d-VCC}, admits a kernel with {𝒪}(d⁴k) vertices and {𝒪}(d⁵k) edges. Both of our kernelization algorithms run in time 𝒪(1.253^d ⋅ (kd)^{𝒪(1)} ⋅ n log n). It is important to note that, unless the Exponential Time Hypothesis (ETH) fails, the dependence on d cannot be improved to 2^{o(d)}, as the case k = 0 reduces to solving the classical Vertex Cover problem, which is known to require 2^{Ω(d)} time under ETH. A key ingredient in our kernelization algorithms is a structural result about the hereditary graph class 𝒢_d, consisting of graphs in which every connected component has vertex cover number at most d. We show that 𝒢_d admits a finite obstruction set (with respect to the induced subgraph relation) of size 2^{𝒪(d²)}, where each obstruction graph has at most 3d + 2 vertices. This combinatorial result may be of independent interest.
Cite as

Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh. Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2025.20,
  author =	{Bhyravarapu, Sriram and Kumar, Pritesh and Kundu, Madhumita and Roy, Shivesh K. and Sahiba and Saurabh, Saket},
  title =	{{Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.20},
  URN =		{urn:nbn:de:0030-drops-241276},
  doi =		{10.4230/LIPIcs.MFCS.2025.20},
  annote =	{Keywords: Parameterized complexity, Polynomial Kernels, Vertex Cover, Finite Forbidden Characterization}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact