Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.17345 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914405176836096 |
|---|---|
| author | Huang, Chien-Chung Kakimura, Naonori Kobayashi, Yusuke Terao, Tatsuya |
| author_facet | Huang, Chien-Chung Kakimura, Naonori Kobayashi, Yusuke Terao, Tatsuya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17345 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection Huang, Chien-Chung Kakimura, Naonori Kobayashi, Yusuke Terao, Tatsuya Data Structures and Algorithms 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. |
| title | Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.17345 |