2026-08-21T18:34:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27477 2026-08-21T14:42:41Z ddc:004 open_access

The Parameterized Complexity of Maximum Span on Natural Matroid Classes Kundu, Madhumita Rai, Ashutosh Sahiba Saurabh, Saket Fixed Parameter Tractability W[1]-hardness FPT Approximation Graphic Matroids Cographic Matroids Transversal Matroids Strict Gammoids Gammoids Laminar Matroids 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Madhumita Kundu and Ashutosh Rai and Sahiba and Saket Saurabh 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.95 urn:nbn:de:0030-drops-274775 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.95 eng https://creativecommons.org/licenses/by/4.0/legalcode