Tatsuya Terao

Chien-Chung Huang, Naonori Kakimura, Yusuke Kobayashi et al.

This paper studies randomized polynomial kernelization for the weighted $d$-matroid intersection problem. While the problem is known to have a kernel of size $O(d^{(k - 1)d})$ where $k$ is the solution size, the existence of a polynomial kernel is not known, except for the cases when either all the given matroids are partition matroids~(i.e., the $d$-dimensional matching problem) or all the given matroids are linearly representable. The main contribution of this paper is to develop a new kernelization technique for handling general matroids. We first show that the weighted $d$-matroid intersection problem admits a polynomial kernel when one matroid is arbitrary and the other $d-1$ matroids are partition matroids. Interestingly, the obtained kernel has size $\tilde{O}(k^d)$, which matches the optimal bound~(up to logarithmic factors) for the $d$-dimensional matching problem. This approach can be adapted to the case when $d-1$ matroids in the input belong to a more general class of matroids, including graphic, cographic, and transversal matroids. We also show that the problem has a kernel of pseudo-polynomial size when given $d-1$ matroids are laminar. Our technique finds a kernel such that any feasible solution of a given instance can reach a better solution in the kernel, which is sufficiently versatile to allow us to design parameterized streaming algorithms and faster EPTASs.

Tatsuya Terao

We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two $r \times n$ matrices $M_1$ and $M_2$, and the objective is to find a largest set of columns that are linearly independent in both $M_1$ and $M_2$. We design a $(1 - \varepsilon)$-approximation algorithm with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + r_{*}^ω)$, where $\mathrm{nnz}(M_i)$ denotes the number of nonzero entries in $M_i$ for $i = 1, 2$, $r_{*}$ denotes the maximum size of a common independent set, and $ω< 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 $\tilde{O}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + n r_{*}^{ω- 1})$ time. We also develop a fast $(1 - \varepsilon)$-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a $(1 - \varepsilon)$-approximation algorithm for weighted linear matroid intersection with time complexity $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + r_{*}^ω)$. Our algorithm improves upon the $(1 - \varepsilon)$-approximation algorithm by Huang--Kakimura--Kamiyama [SODA'16 & Math. Program.'19], which runs in $\tilde{O}_{\varepsilon}(\mathrm{nnz}(M_1) + \mathrm{nnz}(M_2) + nr_{*}^{ω- 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.