Covering Vectors by Spaces: Regular Matroids
From MaRDI portal
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 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.
Recommendations
- Covering vectors by spaces: regular matroids
- Covering vectors by spaces in perturbed graphic matroids and their duals
- Matroidal hypervector spaces
- Enumerating matroids and linear spaces
- scientific article; zbMATH DE number 1156642
- Extensions of matroid covering and packing
- The covering number of the elements of a matroid and generalized matrix functions
- On linear spaces and matroids of arbitrary cardinality
- Well-Covered Vector Spaces of Graphs
- On the covering number of a matroid element
Cites work
- Algorithms and Data Structures
- An FPT algorithm for edge subset feedback edge set
- Approximating clique-width and branch-width
- Branch-width and well-quasi-ordering in matroids and graphs.
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Clustering with local restrictions
- Constructive algorithm for path-width of matroids
- Deciding first order properties of matroids
- Decomposition of regular matroids
- Decomposition width of matroids
- Excluding a planar graph from \(\mathrm{GF}(q)\)-representable matroids
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- Finding Branch-Decompositions and Rank-Decompositions
- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction
- Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- scientific article; zbMATH DE number 2089223 (Why is no real title available?)
- scientific article; zbMATH DE number 6515828 (Why is no real title available?)
- scientific article; zbMATH DE number 53949 (Why is no real title available?)
- scientific article; zbMATH DE number 863479 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- scientific article; zbMATH DE number 3368629 (Why is no real title available?)
- Kernelization lower bounds through colors and IDs
- Max-Flow Min-Cut Matroids: Polynomial Testing and Polynomial Algorithms for Maximum Flow and Shortest Routes
- On the Complexity of Some Enumeration Problems for Matroids
- On the inherent intractability of certain coding problems (Corresp.)
- Parameterized algorithms
- Parameterized algorithms to preserve connectivity
- Parameterized graph separation problems
- Recognizing graphic matroids
- Solving Rota's conjecture
- Spanning circuits in regular matroids
- Testing branch-width
- The Complexity of Multiterminal Cuts
- The highly connected matroids in minor-closed classes
- The intractability of computing the minimum distance of a code
- The minimum k-way cut of bounded size is fixed-parameter tractable
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- The steiner problem in graphs
Cited in
(5)
This page was built for publication: Covering Vectors by Spaces: Regular Matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4555045)
