Header menu link for other important links
X
Deterministic Truncation of Linear Matroids
L. Daniel, P. Misra, , S. Saurabh
Published in Association for Computing Machinery
2018
Volume: 14
   
Issue: 2
Abstract
Let M = (E, I) be a matroid of rank n. A k-truncation of M is a matroid M = (E, I) such that for any A ⊆ E, A ∊ ∊ Í if and only if |A| = k and A - I. Given a linear representation, A, of M, we consider the problem of finding a linear representation, Ak, of the k-truncation of M. A common way to compute Ak is to multiply the matrix A with a random k × n matrix, yielding a simple randomized algorithm. Thus, a natural question is whether we can compute Ak deterministically. In this article, we settle this question for matrices over any field in which the field operations can be done efficiently. This includes any finite field and the field of rational numbers (Q). Our algorithms are based on the properties of the classical Wronskian determinant, and the folded Wronskian determinant, which was recently introduced by Guruswami and Kopparty [23, 24] and Forbes and Shpilka [14]. Our main conceptual contribution in this article is to show that the Wronskian determinant can also be used to obtain a representation of the truncation of a linear matroid in deterministic polynomial time. An important application of our result is a deterministic algorithm to compute representative sets over linear matroids, which derandomizes a result of Fomin et al. [11, 12]. This result derandomizes several parameterized algorithms, including an algorithm for-Matroid Parity to which several problems, such as-Matroid Intersection, can be reduced. © 2018 ACM. All Rights Reserved.
About the journal
JournalData powered by TypesetACM Transactions on Algorithms
PublisherData powered by TypesetAssociation for Computing Machinery
ISSN15496325