Faster Approximate Linear Matroid Intersection
Tatsuya Terao · 2026
Read Faster Approximate Linear Matroid Intersection by Tatsuya Terao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11725.txt.
Introduction
Terao gives a faster approximation method for linear matroid intersection. The task is finding the largest set of columns independent in two given matrices. His method lands within a factor of one minus epsilon of optimal, in time set by the number of nonzero entries plus the optimum size raised to the matrix-multiplication exponent. The same approach handles the weighted version, improving on earlier algorithms by Harvey and by Cheung, Kwok, and Lau.
Catalog record
| CREATOR | Tatsuya Terao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91047 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.11725
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster Approximate Linear Matroid Intersection Tatsuya Terao Abstract We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two r × n r\times n matrices M 1 M_{1} and M 2 M_{2} , and the objective is to find a largest set of columns that are linearly independent in both M 1 M_{1} and M 2 M_{2} . We design a ( 1 − ε ) (1-\varepsilon) -approximation algorithm with time complexity O ~ ε ( nnz ( M 1 ) + nnz ( M 2 ) + r ∗ ω ) \tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega}) , where nnz ( M i ) \mathrm{nnz}(M_{i}) denotes the number of nonzero entries in M i M_{i} for i = 1 , 2 i=1,2 , r ∗ r_{*} denotes the maximum size of a common independent set, and ω < 2.372 \omega<2.372 denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS’06 & SICOMP’09] and Cheung–Kwok–Lau [STOC’12 & JACM’13], which runs in O ~ ( nnz ( M 1 ) + nnz ( M 2 ) + n r ∗ ω − 1 ) \tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega-1}) time. We also develop a fast ( 1 − ε ) (1-\varepsilon) -approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a ( 1 − ε ) (1-\varepsilon) -approximation algorithm for weighted linear matroid intersection with time complexity O ~ ε ( nnz ( M 1 ) + nnz ( M 2 ) + r ∗ ω ) \tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega}) . Our algorithm improves upon the ( 1 − ε ) (1-\varepsilon) -approximation algorithm by Huang–Kakimura–Kamiyama [SODA’16 & Math. Program.’19], which runs in O ~ ε ( nnz ( M 1 ) + nnz ( M 2 ) + n r ∗ ω − 1 ) \tilde{O}_{\varepsilon}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega-1}) time. To obtain these results, we combine Quanrud’s adaptive sparsification framework [ICALP’24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest. Research Institute for Mathematical Sciences, Kyoto University and https://otera99.github.io/ [email protected]://orcid.org/0000-0002-3530-2194 We thank Yusuke Kobayashi for his insightful comments, generous support, and valuable feedback on the manuscript. In particular, his input greatly helped us establish Lemma 11 . We also thank Kou Hamada for helpful conversations that contributed to the initial motivation for this work. We are grateful to Takashi Noguchi for his helpful comments, which simplified the proof of Lemma 11 . Finally, we thank the anonymous reviewers for their careful reading and valuable suggestions. This work was partially supported by the joint project of Kyoto University and Toyota Motor Corporation, titled “Advanced Mathematical Science for Mobility Society” and by JSPS KAKENHI Grant Number JP24KJ1494. keywords Linear matroid intersection, fast approximation algorithm ccs Theory of computation Algorithm design techniques ccs Mathematics of computing Matroids and greedoids † † runningauthor: T. Terao † † copyright: Tatsuya Terao 1 Introduction Fast Algorithms for Linear Matroid Problems Matroids are combinatorial structures that abstract linear independence and provide a unifying framework capturing fundamental properties of matrices and graphs. We focus on fast algorithms for problems on linear matroids that are given explicitly as the columns of an r\times n matrix M over a field \mathbb{F} . Motivated by the view that running time should reflect not only the matrix dimensions r\times n but also its sparsity, we design faster algorithms whose complexity depends on \mathrm{nnz}(M) (the number of nonzero entries of M ) in addition to r and n . In fact, many commonly studied matroids admit sparse linear representations. For example, it is well known that a graphic matroid can be represented by a vertex-edge incidence matrix with exactly two nonzero entries per edge, resulting in a total of 2m nonzero entries, where m is the number of edges (see e.g., [ 49 , Section 5.1] ). From this perspective, an important contribution is due to Cheung–Kwok–Lau [ 14 ] , who developed a remarkable sketching technique and, as a result, presented a surprising algorithm for computing the rank of a matrix M in \tilde{O}(\mathrm{nnz}(M)+(\mathrm{rank}(M))^{\omega}) time. 1 1 1 The \tilde{O} notation omits polylog factors. Note that even checking whether a given subset of vectors is independent already requires O((\mathrm{rank}(M))^{\omega}) time, and reading the input takes O(\mathrm{nnz}(M)) time. Nguy \tilde{\hat{\text{e}}} n [ 47 ] presented an elegant algorithm for computing a maximum-weight base of a linear matroid represented by a matrix M . While a direct application of the sketching technique of Cheung–Kwok–Lau would only yield a running time of \tilde{O}\!\big(\mathrm{nnz}(M)+n\cdot(\mathrm{rank}(M))^{\omega-1}\big) , his refined use of this technique leads to \big(\mathrm{nnz}(M)+(\mathrm{rank}(M))^{\omega}\big)^{1+o(1)} . This problem has also been studied, under the name column rank profile problem [ 19 , 38 , 54 , 20 ] , which asks for the lexicographically smallest sequence of \mathrm{rank}(M) column indices such that the corresponding columns of the matrix are linearly independent. Dumas–Pernet–Sultan [ 20 ] achieved the same time complexity for the column rank profile problem. Linear Matroid Intersection. In this work, we consider fast approximation algorithms for linear matroid intersection. This linear matroid intersection problem can be described without relying on matroid terminology as follows: Given two r\times n matrices M_{1} and M_{2} over a field \mathbb{F} , where the columns in M_{1} and M_{2} are indexed by \{1,\ldots,n\} , the objective is to find a set I\subseteq\{1,\ldots,n\} of maximum size such that the columns indexed by I are linearly independent in both M_{1} and M_{2} . Many important problems in combinatorial optimization, such as bipartite matching, rainbow spanning tree, arborescence, and spanning tree packing, can be viewed as special cases of linear matroid intersection. For the linear matroid intersection problem, Cunningham [ 16 ] gave a combinatorial algorithm with time complexity \tilde{O}(nr^{2}) . Gabow–Xu [ 30 , 31 ] proposed a faster combinatorial algorithm with time complexity \tilde{O}(nrr_{*}^{1/(4-\omega)})=O(nrr_{*}^{0.62}) , where \omega is the exponent of matrix multiplication, known to satisfy \omega<2.371339 [ 3 ] . Here, r_{*} denotes the maximum size of a common independent set. Harvey [ 35 ] developed an algebraic algorithm with time complexity O(nr^{\omega-1}) . Cheung–Kwok–Lau [ 14 ] combined their elegant sketching technique with Harvey’s algorithm [ 35 ] , obtaining an algorithm with running time \tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+nr_{*}^{\omega-1}) . In fact, simply applying their sketching technique reduces an r\times n input matrix to an O(r_{*})\times n matrix while preserving linear dependence among the columns. Given the progress on the case of a single matroid [ 14 , 20 , 47 ] , it is natural to ask whether linear matroid intersection can be solved in \tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega}) time. Note that even checking whether a given subset is independent in a single matroid already requires O(r_{*}^{\omega}) time, and reading the input takes O(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})) time. Avoiding the dependence on n is most meaningful when r_{*}\ll n , a regime that arises naturally, for example, for graphic matroids. However, achieving a running time of \tilde{O}(\mathrm{nnz}(M_{1})+\mathrm{nnz}(M_{2})+r_{*}^{\omega}) seems quite challenging. To achieve such a running time, one must avoid explicitly computing the product of an O(r_{*})\times n matrix and an n\times O(r_{*}) matrix, which would