Can I read Covering vectors by spaces: Regular matroids on EtoBox?

Covering vectors by spaces: Regular matroids by Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket is a scholarly article available to read on EtoBox.

What is Covering vectors by spaces: Regular matroids about?

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 that the linear span of F contains all vectors of T. For graphic matroids this problem is essentially Stainer Forest and for cographic matroids this is a generalization of Multiway Cut. Our main result is the algorithm with running time 2^{O(k)}||M|| ^{O(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.

Author

Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket

Published

2017

Language

EN