Linear Matroid Intersection is in Catalytic Logspace
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912577694466048 |
|---|---|
| author | Agarwala, Aryan Alekseev, Yaroslav Vinciguerra, Antoine |
| author_facet | Agarwala, Aryan Alekseev, Yaroslav Vinciguerra, Antoine |
| contents | Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more.
We study this problem in the model of catalytic computation: space-bounded machines are granted access to \textit{catalytic space}, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation.
Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of $\mathsf{P}$. We address this problem for the class catalytic logspace ($\mathsf{CL}$) with a polynomial time bound ($\mathsf{CLP}$).
Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class $\mathsf{CLP}\subseteq \mathsf{P}$. This was the first subclass of $\mathsf{P}$ shown to contain bipartite matching, and additionally the first problem outside $\mathsf{TC}^1$ shown to be contained in $\mathsf{CL}$. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in $\mathsf{CLP}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06435 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear Matroid Intersection is in Catalytic Logspace Agarwala, Aryan Alekseev, Yaroslav Vinciguerra, Antoine Computational Complexity 68Q15 F.1.3 Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to \textit{catalytic space}, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of $\mathsf{P}$. We address this problem for the class catalytic logspace ($\mathsf{CL}$) with a polynomial time bound ($\mathsf{CLP}$). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class $\mathsf{CLP}\subseteq \mathsf{P}$. This was the first subclass of $\mathsf{P}$ shown to contain bipartite matching, and additionally the first problem outside $\mathsf{TC}^1$ shown to be contained in $\mathsf{CL}$. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in $\mathsf{CLP}$. |
| title | Linear Matroid Intersection is in Catalytic Logspace |
| topic | Computational Complexity 68Q15 F.1.3 |
| url | https://arxiv.org/abs/2509.06435 |