Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR25-138 | 28th September 2025 13:03

Linear Matroid Intersection is in Catalytic Logspace

RSS-Feed




Revision #1
Authors: Aryan Agarwala, Yaroslav Alekseev, Antoine Vinciguerra
Accepted on: 28th September 2025 13:03
Downloads: 102
Keywords: 


Abstract:

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 $P$. We address this problem for the class catalytic logspace ($CL$) with a polynomial time bound ($CLP$).

Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class $CLP\subseteq P$. This was the first subclass of $P$ shown to contain bipartite matching, and additionally the first problem outside $TC^1$ shown to be contained in $CL$. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in $CLP$.


Paper:

TR25-138 | 8th September 2025 10:23

Linear Matroid Intersection is in Catalytic Logspace





TR25-138
Authors: Antoine Vinciguerra
Publication: 28th September 2025 12:21
Downloads: 45
Keywords: 


Abstract:

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 $P$. We address this problem for the class catalytic logspace ($CL$) with a polynomial time bound ($CLP$).

Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class $CLP\subseteq P$. This was the first subclass of $P$ shown to contain bipartite matching, and additionally the first problem outside $TC^1$ shown to be contained in $CL$. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in $CLP$.



ISSN 1433-8092 | Imprint