Linear Matroid Intersection is in Quasi-NC
- PDF / 501,060 Bytes
- 42 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 173 Views
computational complexity
LINEAR MATROID INTERSECTION IS IN QUASI-NC Rohit Gurjar and Thomas Thierauf
Abstract. Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. In case of linear matroids, the problem had a randomized parallel algorithm but no deterministic one. We give an almost complete derandomization of this algorithm, which implies that the linear matroid intersection problem is in quasi-NC. That is, it has uniform circuits of quasi-polynomial size nO(log n) and O(polylog(n)) depth. Moreover, the depth of the circuit can be reduced to O(log2 n) in case of zero characteristic fields. This generalizes a similar result for the bipartite perfect matching problem. Our main technical contribution is to derandomize the Isolation lemma for the family of common bases of two matroids. We use our isolation result to give a quasi-polynomial time blackbox algorithm for a special case of Edmonds’ problem, i.e., singularity testing of a symbolic matrix, when the given matrix is of the form A0 + A1 x1 + · · · + Am xm , for an arbitrary matrix A0 and rank-1 matrices A1 , A2 , . . . , Am . This can also be viewed as a blackbox polynomial identity testing algorithm for the corresponding determinant polynomial. Another consequence of this result is a deterministic solution to the maximum rank matrix completion problem. Finally, we use our result to find a deterministic representation for the union of linear matroids in quasi-NC. Keywords. Matroid Intersection, Isolation Lemma, Derandomization, Polynomial Identity Testing. Subject classification. 90C57, 68W10, 05B35, 68W20.
9 Page 2 of 42
Gurjar & Thierauf
cc
1. Introduction Matroids are combinatorial structures that generalize the notion of linear independence in Linear Algebra. A matroid M is a pair M = (E, I), where E is the finite ground set and I ⊆ P(E) is a family of subsets of E that are said to be the independent sets. There are two axioms the independent sets must satisfy: (1) closure under subsets and (2) the augmentation property – for any two independent sets of different sizes, the smaller one can be augmented with an element from the bigger one to obtain a new independent set (see the Preliminary Section for exact definitions). Matroids are motivated by Linear Algebra. For an n × m matrix V over some field, let v1 , v2 , . . . , vm be the column vectors of V , in this order. We define the ground set E = {1, 2, . . . , m} as the set of indices of the columns of V . A set I ⊆ E is defined to be independent, if the collection of vectors vi , for i ∈ I, is linearly independent. Then M = (E, I) is a matroid: Any subset of an independent set is again independent. The augmentation property is equivalent to the Steinitz Exchange Lemma for two bases of the vector space spanned by the column vectors of V . A matroid is called linear, if it can be represented by a matrix in the above sense over some field. Although we will formulate most of our results in terms of general matroids, our main result
Data Loading...
