Covering Vectors by Spaces: Regular Matroids

Abstract

Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. 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, in the Space Cover problem, 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 the linear span of $F$ contains all vectors of $T$. For graphic matroids this problem is essentially Steiner Forest and for cographic matroids this is a generalization of Multiway Cut. Our main result is the algorithm with running time $2^{\mathcal{O}h(k)}\cdot ||M|| ^{\mathcal{O}h(1)}$ solving Space Cover 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 on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace.