License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.56
URN: urn:nbn:de:0030-drops-73865
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7386/
Fomin, Fedor V. ;
Golovach, Petr A. ;
Lokshtanov, Daniel ;
Saurabh, Saket
Covering Vectors by Spaces: Regular Matroids
Abstract
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.
BibTeX - Entry
@InProceedings{fomin_et_al:LIPIcs:2017:7386,
author = {Fedor V. Fomin and Petr A. Golovach and Daniel Lokshtanov and Saket Saurabh},
title = {{Covering Vectors by Spaces: Regular Matroids}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {56:1--56:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7386},
URN = {urn:nbn:de:0030-drops-73865},
doi = {10.4230/LIPIcs.ICALP.2017.56},
annote = {Keywords: regular matroids, spanning set, parameterized complexity}
}
|
Keywords: |
|
regular matroids, spanning set, parameterized complexity |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
