2026-07-27T21:43:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7386 2024-03-06T10:40:23Z ddc:004 open_access

Covering Vectors by Spaces: Regular Matroids Fomin, Fedor V. Golovach, Petr A. Lokshtanov, Daniel Saurabh, Saket regular matroids spanning set parameterized complexity We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, we study the Space Cover problem, where we are given a matrix M and a subset of its columns T; the task is to find a minimum set F of columns of M disjoint with T such that that the linear span of F contains all vectors of T. This is a fundamental problem arising in different domains, such as coding theory, machine learning, and graph algorithms. We give a parameterized algorithm with running time 2^{O(k)}||M|| ^{O(1)} solving this problem in the case when M is a totally unimodular matrix over rationals, where k is the size of F. In other words, we show that the problem is fixed-parameter tractable parameterized by the rank of the covering subspace. The algorithm is "asymptotically optimal" for the following reasons. Choice of matrices: Vector matroids corresponding to totally unimodular matrices over rationals are exactly the regular matroids. It is known that for matrices corresponding to a more general class of matroids, namely, binary matroids, the problem becomes W[1]-hard being parameterized by k. Choice of the parameter: The problem is NP-hard even if |T|=3 on matrix-representations of a subclass of regular matroids, namely cographic matroids. Thus for a stronger parameterization, like by the size of T, the problem becomes intractable. Running Time: The exponential dependence in the running time of our algorithm cannot be asymptotically improved unless Exponential Time Hypothesis (ETH) fails. Our algorithm exploits the classical decomposition theorem of Seymour for regular matroids. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Daniel Lokshtanov and Saket Saurabh 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.56 urn:nbn:de:0030-drops-73865 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.56 eng https://creativecommons.org/licenses/by/3.0/legalcode