<p>Formally speaking, the matroid intersection problem is described as follow:</p>
<p>Given two matroids on the ground set <span class="math-container">$E$</span>, namely <span class="math-container">$(E, \mathcal I_1)$</span> and <span class="math-container">$(E, \mathcal I_2)$</span> we are asked to find the set <span class="math-container">$S$</span> with maximum size such that <span class="math-container">$S$</span> is independent in both <span class="math-container">$\mathcal I_1$</span> and <span class="math-container">$\mathcal I_2$</span>.</p>
<p>I found that in 1986, Cunningham has published a paper that given an algorithm to solve this problem correctly in <span class="math-container">$O(nr^{1.5}\mathcal{T}_{\text{ind}})$</span> time where <span class="math-container">$n$</span> is the size of the ground set, <span class="math-container">$r$</span> is the maximum rank of two matroid and <span class="math-container">$\mathcal T_{\text{ind}}$</span> is the complexity of the independent oracles.</p>
<p>However I can't access his paper freely, but i leant that his algorithm is done in similar style with Dinitz's algorithm for maximum flow, via divied into phases and making sure that after every phase the length of the shortest augumenting path is always increased furthermore each phase only take <span class="math-container">$O(nr)$</span> time. I can't figure out how he managed to implement the algorithm using that idea so hopefully someone can share an implementation for his algorithm, or even better, the original paper he published in 1986.</p>

CC BY-SA 4.0
2024-11-02T15:43:29.273Z
Matroid intersection is covered in books/courses on combinatorial optimization and there have been several algorithms since Cunningham's paper. It may be easier to read books than a paper. In any case you can find Schrijver's chapter on matroid intersection at the link: https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-41:MatIntersection.pdf
Chandra Chekuri
CC BY-SA 4.0
2024-11-02T19:36:48.383Z
thank you very much
jackdean
<implementation><matroids>
implementation of Cunningham's matroid intersection algorithm
jackdean
# implementation of Cunningham's matroid intersection algorithm

(Asked by: username_0 on 2024-11-02)

Formally speaking, the matroid intersection problem is described as follow:

Given two matroids on the ground set $E$, namely $(E, \mathcal I\_1)$ and $(E, \mathcal I\_2)$ we are asked to find the set $S$ with maximum size such that $S$ is independent in both $\mathcal I\_1$ and $\mathcal I\_2$.

I found that in 1986, Cunningham has published a paper that given an algorithm to solve this problem correctly in $O(nr^{1.5}\mathcal{T}\_{\text{ind}})$ time where $n$ is the size of the ground set, $r$ is the maximum rank of two matroid and $\mathcal T\_{\text{ind}}$ is the complexity of the independent oracles.

However I can't access his paper freely, but i leant that his algorithm is done in similar style with Dinitz's algorithm for maximum flow, via divied into phases and making sure that after every phase the length of the shortest augumenting path is always increased furthermore each phase only take $O(nr)$ time. I can't figure out how he managed to implement the algorithm using that idea so hopefully someone can share an implementation for his algorithm, or even better, the original paper he published in 1986.

**Tags:** implementation, matroids

> **Comments:**
> **username_1**: Matroid intersection is covered in books/courses on combinatorial optimization and there have been several algorithms since Cunningham's paper. It may be easier to read books than a paper. In any case you can find Schrijver's chapter on matroid intersection at the link: https://page.math.tu-berlin.de/~felsner/Lehre/SemMatS/Literatur/Schrijver-41:MatIntersection.pdf  
> **username_0**: thank you very much  

---

## 0 answers

