We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a “unified” algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows.

Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with $\tO_k(n+r\sqrt{r})$ dynamic-rank-query and time complexities for the matroid union problem over $k$ matroids, where $n$ is the input size,  $r$ is the output size, and
$\tO_k$ hides $\poly(k, \log(n))$. This implies the following consequences.
(i) An improvement over the $\tO_k(n\sqrt{r})$ bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model.
(ii) An $\tO_k\left(|E|+|V|\sqrt{|V|}\right)$-time algorithm for the $k$-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the
$\tO_k\left(|V|\sqrt{|E|}\right)$ bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91].
Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility.

Matroid intersection. We show a matroid intersection algorithm with $\tO(n\sqrt{r})$ dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g.
colorful spanning tree [Gabow-Stallmann ICALP'85],
graphic matroid intersection [Gabow-Xu FOCS'89],
simple scheduling matroid intersection [Xu-Gabow ISAAC'94],
and Hopcroft-Karp combinatorial bipartite matching.
More importantly, this is done via a “unified” algorithm in the sense that an improvement over our dynamic-rank-query algorithm would
imply improved bounds for all the above problems simultaneously.

Lower bounds. We show simple super-linear ($\Omega(n\log n)$) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous $\log_2(3)n - o(n)$ bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19].

§ INTRODUCTION

Via reductions to the max-flow and min-cost flow problems, exciting progress has been recently made for many graph problems such as maximum matching, vertex connectivity, directed cut, and Gomory-Hu trees [63, 60, 64, 80, 53, 58, 6, 79, 57, 5, 9, 22, 59, 41, 7, 23, 78, 4, 21, 20].
However, many basic problems still witness no progress since a few decades ago. These problems include $k$-disjoint spanning trees [45, 37], colorful spanning tree [42], arboricity [38], spanning tree packing [45], graphic matroid intersection [42, 46], and simple job scheduling matroid intersection [85].
For example, in the $k$-disjoint spanning trees problem <cit.>,
we want to find $k$ edge-disjoint spanning trees in a given input graph $G=(V,E)$. When $k=1$, this is the spanning tree problem and can be solved in linear time.
For higher values of $k$, the best runtime remains
$\tO(k^{3/2}|V|\sqrt{|E|})$-time algorithm from around 1990 [45, 37][The stated bound was due to Gabow and Westermann [45]. Gabow [37] announced an improved bound of $O(kn\sqrt{m+kn\log(n)})$ but this bound was later removed from the journal version of the paper.], which is also the best runtime for its applications such as Shannon Switching Game [39] and Graph $k$-Irreducibility [83, 43].
No better runtime was known even for the special case of $k=2$.

Can we improve the
bounds of $k$-disjoint spanning trees and other problems?
More importantly, since it is very unclear if these problems can be reduced to max-flow or min-cost flow[For example, the best-known number of max-flow calls to decide whether there are $k$ disjoint spanning trees and to find the $k$ spanning trees are $O(n)$ and $O(n^2)$ respectively.],
is there an alternative approach to designing fast algorithms for many problems simultaneously?
Fortunately, many of the above problems can be modeled as matroid problems, giving hope that solving matroid problems would solve many of these problems in one shot. Unfortunately, this is not true in the traditional model for matroid problems—even the most efficient algorithm possible for a matroid problem does not
necessarily give a faster algorithm for any of its special cases.
We discuss this more below.

Matroid Problems. A matroid $\cM$ is a pair $(U, \cI)$ where $U$ is a finite set (called the ground set) and $\cI$ is a family of subsets of $U$ (called the independent sets) satisfying some constraints (see <ref>; these constraints are not important in the following discussion).
Since $\cI$ can be very large, problems on matroid $\cM$ are usually modeled with oracles that answer queries. Given a set $S\subseteq U$, independence queries ask if $S\in \cI$ and rank queries ask for the value of $\max_{I\in \cI, I\subseteq S} |I|.$
Two textbook examples of matroid problems are matroid intersection and union[Matroid union is also sometimes called matroid sum.] (e.g., <cit.>).
We will also consider the special case of matroid union called $k$-fold matroid union.

(I) In matroid intersection, we are given two matroids $(U, \cI_1)$ and $ (U, \cI_2)$ and want to find a set of maximum size in $\cI_1\cap \cI_2.$
(II) In matroid union, we are given $k$ matroids $(U_1, \cI_1), (U_2, \cI_2), \ldots, (U_k, \cI_k)$, and want to find the set $S_1\cup S_2 \cup \cdots \cup S_k$, where $S_i \in \cI_i$ for every $i$, of maximum size.
(III) Matroid union in the special case where $U_1=U_2=\cdots = U_k$ and $\cI_1=\cI_2=\cdots = \cI_k$ is called  $k$-fold matroid union.

Notations: Throughout, for problems over matroids  $(U_1, \cI_1), (U_2, \cI_2), \ldots, (U_k, \cI_k)$, we define  $n:=\max_i{|U_i|}$ and $r:=\max_{i}\max_{S \in \cI_i}|S|$.

Matroid problems are powerful abstractions that can model many fundamental problems.
For example, the $2$-disjoint spanning tree problem can be modeled as a $2$-fold matroid union problem:
[breakable,boxrule=0pt,frame hidden,sharp corners,enhanced,borderline west=.5 pt0ptred,colback=white]

Given a graph $G=(V, E)$, let $\cM=(U, \cI)$ be the corresponding graphic matroids, i.e. $U=E$ and $S\subseteq E$ is in $\cI$ if it is a forest in $G$. (It is a standard fact that such an $\cM$ is a matroid.)
The $2$-fold matroid union problem with input $\cM$ is a problem of finding two forests $F_1\subseteq E$ and $F_2\subseteq E$ in $G$ that maximizes $|F_1\cup F_2|$. This is known as the $2$-forest problem which clearly generalizes $2$-disjoint spanning tree  (a $2$-forest algorithm will return two disjoint spanning trees in $G$ if they exist).

Observe that this argument can be generalized to modeling the $k$-disjoint spanning trees problem by $k$-fold matroid union.
Other problems that can be modeled as matroid union (respectively, matroid intersection) include arboricity,  spanning tree packing, $k$-pseudoforest, and mixed $k$-forest-pseudoforest (respectively, bipartite matching and colorful spanning tree).

The above fact makes matroid problems a unified approach for showing that many problems, including those mentioned above, can be solved in polynomial time. This is because (i) the matroid union, intersection, and other problems can be solved in polynomial time and rank/independence queries, and (ii) for most problems  queries can be answered in polynomial time. For example, when we model $k$-disjoint spanning trees as $k$-fold graphic matroid union like above, the corresponding rank query is: given a set $S$ of edges, find the size of a spanning forest of $S$. This can be solved in $O(|S|)$ time.

When it comes to more fine-grained time complexities, such as nearly linear and sub-quadratic time, matroid algorithms in the above model are not very helpful. This is because simulating a matroid algorithm in this model causes too much runtime blow-up.
For example, even if we can solve $k$-fold matroid union over $(U, \cI)$ in linear ($O(|U|)$) rank query complexity, it does not necessarily imply that we can solve its special case of $2$-disjoint spanning tree any faster.
This is because each query about a set $S$ of edges needs at least $O(|S|)$ time even to specify $S$, which can be as large as the number of edges in the input graph.
In other words, even a matroid union algorithm with linear complexities may only imply $O(|E|^2)$ time for solving 2-disjoint spanning trees on graphs $G=(V,E)$.
This is also the case for other problems that can be modeled as matroid union and intersection.
Because of this, previous works obtained improved bounds by simulating an algorithm for matroid problems and coming up with clever ideas to speed up the simulation for each of these problems one by one (e.g., [44, 74, 42, 45, 36, 46, 37, 85]).
It cannot be guaranteed that recent and future improved algorithms for matroid problems (e.g., [24, 17, 15]) would imply improved bounds for any of these problems.

Dynamic Oracle.
The main conceptual contribution of this paper is an introduction of a new matroid model called dynamic oracle
and an observation that, using dynamic algorithms,
solving a matroid problem efficiently in our model immediately implies efficient algorithms for many problems it can model.
In contrast to traditional matroids where a query can be made with an arbitrary set $S$, our model only allows queries made by slightly modifying the previous queries.[The “cost” of a query in our dynamic model is the distance (size of the symmetric difference) from some (not necessarily the last) previous query.] More precisely, the dynamic-rank-oracle model, which is the focus of this work, is defined as follows.[One can also define the dynamic-independence-oracle model where $\textsc{Query}(i)$ returns only the independence of $S_i$.]

For a matroid $\cM = (\ground, \cI)$, starting from $S_0 = \emptyset$ and $k = 0$, the algorithm can access the oracle via the following three operations.

* $\textsc{Insert}(v, i)$: Create a new set $S_{k + 1} := S_i \cup \{v\}$ and increment $k$ by one.

* $\textsc{Delete}(v, i)$: Create a new set $S_{k + 1} := S_i \setminus \{v\}$ and increment $k$ by one.

* $\textsc{Query}(i)$: Return the rank of $S_i$, i.e., the size of the largest independent subset of $S_i$.

We say that a matroid algorithm takes $t$ time and dynamic-rank-query complexities if its time complexity and required number of operations are both at most $t$.

We emphasize that a query can be obtained from any previous query, not just the last one.

matroid problems

special cases

$k$-fold matroid union in $T(n, r, k)$

$k$-forest in $\tT(|E|, |V|, k))$

$k$-pseudoforest in $\tT(|E|, |V|, k))$

$k$-disjoint spanning tree in $\tT(|E|, |V|, k)$ (randomized)

$k$-disjoint spanning tree in $\hat{T}(|E|, |V|, k)$ (deterministic)

arboricity in $\tT(|E|, |V|, \sqrt{|E|}))$

tree packing in $\tT(|E|, |V|, |E|/|V|))$

Shannon Switching Game in $\tT(|E|, |V|, 2))$

graph $k$-irreducibility in $\tT(|E|, |V|, k))$

matroid union in $T(n, r, k)$

$(f, p)$-mixed forest-pseudoforest in $\tT(|E|, |V|, f + p))$

matroid intersection in $T(n, r)$

bipartite matching in $\tT(|E|, |V|)$

colorful spanning tree in $\tT(|E|, |V|)$

graphic matroid intersection in $\tT(|E|, |V|)$

simple job scheduling matroid intersection in $\tT(n, r)$

convex transversal matroid intersection in $\tT(|V|, \mu)$

Examples of implications of dynamic-rank-oracle matroid algorithms. The complexities in the first column are in terms of time and dynamic-rank-query complexities. Notations $n$, $r$, and $k$ are as in <Ref>.
In the second column, the $\polylog{n}$ factors are hidden in $\tT$ and
subpolynomial factors are hidden in $\hat{T}.$ Details are in  <ref>.

[Details in  <ref>]
Algorithms for the $k$-fold matroid union, matroid union, and matroid intersection problems imply algorithms for a number of problems with time complexities shown in <Ref>.

As an example, we sketch the proof that if $k$-fold matroid union can be solved in $T(n, r, k)$ then $k$-disjoint spanning trees can be found in  $T(|E|, |V|, k)\cdot\polylog(|V|)$ time.
Recall that in the traditional rank-oracle model, the algorithm can ask an oracle for the size of a spanning forest in an arbitrary set of edges $S$, causing $O(|S|)$ time to simulate.
In our dynamic-rank-oracle model, an algorithm needs to modify some set $S_i$ to the desired set $S$ using the Insert and Delete operations before asking for the size of a spanning forest in $S$. We can use a spanning forest data structure to keep track of the size of the spanning forest under edge insertions and deletions. This takes $\polylog(|V|)$ time per operation [52, 40].[The dynamic spanning forest algorithms of [52, 40] are randomized and assume the so-called oblivious adversary (as opposed to, e.g.,   [69, 84] which work against adaptive adversaries). This is not a problem because we only need to report the size of the spanning forest and not an actual forest. We can also use a deterministic algorithm from [19, 70] which requires $|V|^{o(1)}$ time per operation.]
So, if $k$-fold matroid union can be solved in $T(n, r, k)$ time and dynamic rank queries, then $k$-disjoint spanning trees can be solved in  $\tO(T(n, r, k))=\tO(T(|E|, |V|, k))$ time, where the equality is because the ground set size is the number of edges ($|U|=|E|$) and the rank $r$ is equal to the size of a spanning forest (thus at most $|V|$).[Note that we also need a fully-persistent data structure [29, 27] to maintain the whole change history in our argument.]

Observe that designing efficient algorithms in our dynamic-oracle model is not easier than in the traditional model: a dynamic-oracle matroid algorithm can be simulated in the traditional model within the same time and query complexities. Naturally, the first challenge of the new model is this question: Can we get matroid algorithms in the new model whose performances match the state-of-the-art algorithms in the traditional model?
Moreover, for the new model to provide a unified approach to solve many problems simultaneously, one can further ask: Would these new matroid algorithms imply state-of-the-art bounds for many problems?

In this paper, we provide algorithms in the new model whose complexities not only match those in the traditional model but sometimes even improve them.  These lead to new bounds for some problems and, for other problems, a unified algorithm whose performance matches previous results developed in various papers for various problems.

More precisely, the best time and rank-query complexities for matroid intersection on input $(U, \cI_1)$ and $(U, \cI_2)$ were $\tO(n\sqrt{r})$ by Chakrabarty, Lee, Sidford, Singla, and Wong [24] (improving the previous $\tO(nr)$ bound based on Cunningham's classic algorithm [26, 61, 67]).
Due to a known reduction, this implies $\tO(k^2\sqrt{k}n\sqrt{r})$ bound for $k$-fold matroid union and matroid union.
In this paper, we present algorithms in the dynamic-oracle model that imply improved bounds in the traditional model for $k$-fold matroid union and matroid union and match the bounds for matroid intersection.

Here, we only state our dynamic-rank-query complexities as they are the main focus of this paper, and for all the applications we have, answering (and maintaining dynamically) independence queries does not seem to be significantly easier.
Note that we also obtain dynamic-independence-query algorithms that match the state-of-the-art traditional ones [15] which we defer to <ref>.

(I)  $k$-fold matroid union over input $(\ground, \cI)$ can be solved in $\tO(n + kr\sqrt{\min(n, kr)} + k \min(n, kr))$ time and dynamic rank queries.
(II) Matroid union over input $(\ground_1, \cI_1), (\ground_2, \cI_2), \ldots, (\ground_k, \cI_k)$ can be solved in $\tO\left(\left(n + r\sqrt{r}\right) \cdot \poly(k)\right)$ time and dynamic rank queries.
(III) Matroid intersection over input $(\ground, \cI_1)$ and $(\ground, \cI_2)$ can be solved in $\tO(n\sqrt{r})$ time and dynamic rank queries.

problems     our bounds     state-of-the-art results
(Via $k$-fold matroid union)

$k$-forest[For $k$-forest and its related graph problems in the table, we can assume that $k \leq |V|$, and thus the $k^2r$ (where $r = \Theta(|V|)$) term in <ref> is dominated by the $(kr)^{3/2}$ term.]     $\tO(|E| + (k|V|)^{3/2})$      $\tO(k^{3/2}|V|\sqrt{|E|})$ [45]

$k$-pseudoforest     $\tO(|E| + (k|V|)^{3/2})$      $|E|^{1 + o(1)}$ [21]

$k$-disjoint spanning trees     $\tO(|E| + (k|V|)^{3/2})$      $\tO(k^{3/2}|V|\sqrt{|E|})$ [45]

arboricity[Here we use the bound that $\alpha \leq \sqrt{E}$ [38].]     $\tO(|E||V|)$      $\tO(|E|^{3/2})$ [38]

tree packing     $\tO(|E|^{3/2})$     $\tO(|E|^{3/2})$ [45]

Shannon Switching Game     $\tO(|E| + |V|^{3/2})$      $\tO(|V|\sqrt{|E|})$ [45]

graph $k$-irreducibility     $\tO(|E| + (k|V|)^{3/2} + k^2|V|)$      $\tO(k^{3/2}|V|\sqrt{|E|})$ [45]

(Via matroid union)

$(f, p)$-mixed forest-pseudoforest     $\tO_{f,p}(|E| + |V|\sqrt{|V|})$      $\tO((f + p)|V|\sqrt{f|E|})$ [45]

(Via matroid intersection)

bipartite matching (combinatorialfoot:combinatorial)     $\tO(|E|\sqrt{|V|})$     $O(|E|\sqrt{|V|})$ [49]

bipartite matching (continuous)     $\tO(|E|\sqrt{|V|})$      $|E|^{1 + o(1)}$ [21]

graphic matroid intersection     $\tO(|E|\sqrt{|V|})$     $\tO(|E|\sqrt{|V|})$ [46]

simple job scheduling matroid intersection     $\tO(n\sqrt{r})$     $\tO(n\sqrt{r})$ [85]

convex transversal matroid intersection     $\tO(|V|\sqrt{\mu})$     $\tO(|V|\sqrt{\mu})$ [85]

linear matroid intersection[Our bound is with respect to the current value of $\omega < 2.37286$ [12]. If $\omega = 2$, then our bound becomes $\tO(n^{2.5}\sqrt{r})$.]     $\tO(n^{2.529}\sqrt{r})$      $\tO(nr^{\omega - 1})$ [48]

colorful spanning tree     $\tO(|E|\sqrt{|V|})$     $\tO(|E|\sqrt{|V|})$ [42]

maximum forest with deadlines     $\tO(|E|\sqrt{|V|})$      (no prior work)

Implications of our matroid algorithms stated in <ref> in comparison with previous results. Results marked with a  improve over the previous ones. Results marked with a  are worse than the best time bounds. Other results match the currently best-known algorithms up to poly-logarithmic factors. Details can be found in <ref>.

Combined with <Ref>, the above theorem immediately implies fast algorithms for many problems. <Ref> shows some of these problems.
One of our highlights is the improved bounds for $k$-forest and $k$-disjoint spanning trees. Even for $k=2$, there was no runtime better than the decades-old $\tO(k^{3/2}|V|\sqrt{|E|})$ runtime [45, 37]. Our result improves this to  $\tO(|E| + (k|V|)^{3/2})$.
This is nearly linear for dense input graphs and small $k$.
This also implies a faster runtime for, e.g., Shannon Switching Game (see [76, 45]) which is a special case of $2$-disjoint spanning trees.

Our matroid intersection algorithm gives a unified approach to achieving time complexities that were previously obtained by various techniques in many papers.
Thus, improving this algorithm would imply breakthrough runtimes for many of these problems simultaneously.
Moreover, in contrast to the previous approach where matroid algorithms have to be considered for each new problem one by one, our approach has the advantage that it can be easier to derive new bounds.
For example, say we are given a graph $G = (V, E)$, where the edge $e$ will stop functioning after day $d(e)$.
Every day we can “repair” one functioning edge.
Our goal is to make the graph connected in the long run  (an edge will work forever once it has been repaired).
This is the maximum forest with deadlines problem.
Formally speaking, the goal is to construct a spanning tree or a forest of the maximum size at the end, by selecting an edge $e$ with $d(e) \geq t$ in the $t^{\scriptsize \mbox{{\rm th}}}$ round.[It is tempting to believe that we can use a greedy algorithm where we always select an edge $e$ with the smallest $d(e)$ to the solution. The following example shows why this does not work: There are three vertices $V=\{a,b,c,d\}$. Edges $e_1$ and $e_2$ between $a$ and $b$ have $d(e_1)=1$ and $d(e_2)=3$. Edges $e_3=(b,c)$ and $e_4=(c,d)$ have $d(e_3)=d(e_4)=2$.
Our result implies a runtime of  $\tO(|E|\sqrt{|V|})$ for this problem. The runtime holds even for the harder case where each edge is also associated with an arrival time (edges cannot be selected before they arrive).

We also list some problems where our bounds cannot match the best bounds in <Ref>. Improving our matroid algorithms to match these bounds is a very interesting open problem. A particularly interesting case is the maximum bipartite matching problem. Our dynamic-oracle matroid intersection algorithm  implies a runtime that matches the runtime from the best combinatorial algorithm of Hopcroft and Karp [49] which has been recently improved via continuous optimization techniques (e.g., [63, 64, 25, 8, 80, 79, 21]).[The term “combinatorial” is vague and varies in different contexts. Here, an algorithm is “combinatorial” if it does not use any of the continuous optimization techniques such as interior-point methods (IPMs).]
There are barriers to using continuous optimization even to solve some special cases of matroid intersection (e.g. colorful spanning tree's linear program requires exponentially many constraints). Thus, improving our matroid intersection algorithm requires either a new way to use continuous optimization techniques or a breakthrough idea in designing combinatorial algorithms that would improve Hopcroft-Karp algorithm.

Lower Bounds.
Another advantage of our dynamic-oracle matroid model is that it can be easier to prove lower bounds than the traditional model. As a showcase, we show a simple super-linear rank-query lower bound in our new model. In fact, our argument also implies the first super-linear independence-query lower bound in the traditional model.
The latter result might be of independent interest.

(I) Any deterministic algorithms require $\Omega(n\log n)$ dynamic rank queries to solve the matroid union and matroid intersection problems.
(II) Any deterministic algorithms require $\Omega(n\log n)$ (traditional) independence queries to solve the matroid union and matroid intersection problems.

Our first lower bound suggests that the dynamic-oracle model might at best give nearly linear (and not linear) time algorithms.
Prior to this paper, only a $\log_2(3)n - o(n)$ independence-query lower bound for deterministic algorithms was known for (traditional) independence queries, due to Harvey [47].[To the best of our knowledge, this lower bound does not hold for rank queries.]
Our lower bound in the traditional model improves this decade-old bound.
Moreover, showing super-linear independence-query lower bounds in the traditional model for matroid intersection is a long-standing open problem considered since 1976 (e.g. [82, 24]).[As noted by Harvey, Welsh asked about the number of queries
needed to solve the matroid partition problem, which is equivalent to matroid union and intersection.]
Our lower bound in the traditional model answers this open problem for deterministic algorithms. The case of randomized algorithms would be resolved too if an $\omega(|V|)$ lower bound was proved for the communication complexity for computing connectivity of an input graph $G=(V,E)$. (It was conjectured to be $\Omega(n\log n)$ in [3].)

§.§ Techniques

In this section we briefly discuss our technical contributions. For a more in-depth overview of our algorithms, see the technical overview (<ref>).

Exchange Graph & Blocking Flow. Our algorithms and lower bounds are based on the notion of finding augmenting paths in the exchange graph, due to [30, 54, 2].
Given a common independent set $S\in \cI_1\cap \cI_2$, the exchange graph $G(S)$ is a directed graph where finding an $(s,t)$-path corresponds to increasing the size of $S$ by one. Starting with the work of Cunningham [26], modern matroid intersection algorithms (including the state-of-the-art [24, 15]) are based on a “Blocking Flow” idea inspired by the Hopcroft-Karp's [49] bipartite matching and Dinic's [28]  max-flow algorithms.

Matroid Intersection with Dynamic Oracle.
Our matroid intersection algorithms are implementations of the state-of-the-art $\tO(n\sqrt{r})$ rank-query algorithm of [24] and
the $\tO(n r^{3/4})$ independence-query algorithm of [15]. Our contribution here is to show that versions of them can be implemented also in the dynamic-oracle model.

These algorithms explore the exchange graph efficiently in the classic non-dynamic models by performing binary searches with the oracle queries to find useful edges. However, such a binary search is very expensive in the dynamic-oracle model (as the queries differ by a lot): a single such binary search might cost up to $O(n)$ in the dynamic-oracle model instead of just $O(\log n)$.

Our contribution is to design a binary-tree data structure that supports finding these useful edges efficiently also in the dynamic-oracle model.
Note that after each augmentation the underlying exchange graph changes, so the data structure must also support these dynamic updates efficiently. Some updates can just be propagated up the tree, while others we handle by batching them and rebuilding the tree periodically.
We also rely on a structural result “Augmenting Sets” by [24] which states that the updates to the exchange graph are local, which helps us reduce the number of updates we need to make to our data structure, and achieve the final time bound.

Matroid Union with Dynamic Oracle.
Our $\tO(n + r\sqrt{r})$ matroid union algorithm with dynamic rank oracle is based on our $\tO(n \sqrt{r})$ matroid intersection algorithm (indeed, matroid union is a special case of matroid intersection).
We are able to obtain a more efficient algorithm by
taking advantage of the additional structure of the exchange graph in the case of matroid union.
The main idea is to run the blocking flow algorithm only on a dynamically-changing subgraph of size $\Theta(r)$, instead of on the full exchange graph of size $\Theta(n)$.

A crucial observation is that all but $O(r)$ elements will be directly connected to the source vertex $s$. To “sparsify” this first layer in the breadth-first-search tree, we argue that one only needs to consider a basis of it (this basis will have size at most $r$ as opposed to $n$). After an augmentation, this first layer changes, so we design a dynamic algorithm to maintain a basis of a matroid[For example, maintaining a spanning forest in a dynamically changing graph.], with $\tO(\sqrt{r})$ update time and $O(n)$ pre-computation.
Our algorithm to maintain this basis dynamically is inspired by the
dynamic minimum spanning tree algorithm of [35] ($O(\sqrt{|E|})$ update time), in combination with the sparsification trick of [34] ($\tO(\sqrt{|V|})$ update time).
We believe that our dynamic algorithm to maintain a (min-weight) basis of a matroid might also be of independent interest.

Lower Bounds. Our super-linear $\Omega(n \log n)$ query lower bound comes from studying the communication complexity of matroid intersection. The matroids $\cM_1$ and $\cM_2$ are given to two parties Alice and Bob respectively and they are asked to solve the matroid intersection problem using as few bits of communication between them. We show that even if Alice and Bob know some common independent set $S\in \cI_1\cap \cI_2$, they need to communicate $\Omega(n\log n)$ bits to see if $S$ is optimal. Essentially, they need to determine if there is an augmenting path in the exchange graph. Using a class of matroids called gammoids (see e.g. [71, 65]), we show a reduction from the $(s,t)$-connectivity problem which has a deterministic $\Omega(n\log n)$ communication lower bound [50].

§.§ Organization

The rest of the paper is organized as follows.
We first give a high-level overview of how we obtain our algorithms in <ref>.
In <ref>, we provide the necessary preliminaries.
We then construct the binary search tree data structure in <ref>, followed in <ref> by how to use it to implement our $\tO(n\sqrt{r})$ matroid intersection algorithm in the new dynamic-rank-oracle model (the dynamic-independence-oracle algorithm is in <ref>).
In <ref> we describe our data structure to maintain a basis of a matroid dynamically, and then we use this in our $\tO_k(n+r\sqrt{r})$ matroid union algorithm in <ref> (the special case of $k$-fold matroid union is in <ref>).
We show our super-linear lower bound in <ref>. We end our paper with a discussion of open problems in <ref>.
In <ref> we mention how to implement different matroids oracles in the dynamic-oracle model, and discuss some problems we can solve with our algorithms.

§ TECHNICAL OVERVIEW OF ALGORITHMS

§.§ The Blocking-Flow Framework

In this section, we give a high-level overview of our algorithms.
We will focus on the dynamic-rank-oracle model (<ref>), and sketch how to efficiently implement the “blocking flow”[Similar to the Hopcroft-Karp's [49] bipartite matching and Dinic's [28] maximum flow algorithms.] matroid intersection algorithms of [42, 26, 24, 67] in this model.
As such, we briefly recap how the $\tO(n\sqrt{r})$ rank-query (in the traditional oracle model) algorithm of [24] works first, and then explain how to implement their framework in the new dynamic oracle model with the same cost.

Their algorithm, like most of the matroid intersection algorithms, is based on repeatedly finding augmenting paths in exchange graphs (see <ref> for a definition). Say we have already found some common independent set $S\in \cI_1\cap \cI_2$ (we start with $S = \emptyset$). Then the exchange graph $G(S)$ is a directed bipartite graph in which finding an $(s,t)$-path exactly corresponds to increasing the size of $S$ by one.
According to Cunningham's blocking-flow argument [26], if we always augment along the shortest augmenting path, the lengths of such augmenting paths are non-decreasing.
Moreover, if the length of the shortest augmenting path in $G(S)$ is at least $1/\epsilon$, then the size of the current common independent set $S$ must be at least $\left(1 - O(\epsilon)\right) r$ (i.e. it is only $O(\epsilon r)$ away from optimal).
Thus, the “blocking flow”-style algorithms consists of two stages:

* In the first stage, they obtain a $(1 - \epsilon)$-approximate solution by finding augmenting paths until their lengths become more than $O(1/\epsilon)$. This is done by running in phases, where in phase $i$ they eliminate all augmenting paths of length $2i$ by finding a so-called “blocking flow”—a maximal (not necessarily maximum) collection of compatible augmenting paths. Each such phase can be implemented using only $\tO(n)$ rank queries, as shown in [24]. This means that the first stage needs a total of $\tO(n/\epsilon)$ rank-queries (in the classic non-dynamic model).

* In the second stage, they find the remaining $O(\epsilon r)$ augmenting paths one at a time. Each such augmentation can be found in $\tO(n)$ rank queries, for a total of $\tO(\epsilon nr)$ queries for this stage.

Using $\epsilon = 1/\sqrt{r}$, [24] obtains their $\tO(n \sqrt{r})$ rank-query exact matroid intersection algorithm.
The crux of how to implement the stages efficiently is a binary search trick to explore useful edges of the exchange graph quickly (for e.g. to implement a breadth-first-search on the graph). The exchange graph can have up to $\Theta(nr)$ edges in total, but it is not necessary to find all of them. We will argue that this binary search trick (which issues queries far away from each other) can still be implemented in the dynamic-oracle model, with the use of some data structures.

§.§ Matroid Intersection

Binary Search Tree.
The crux of why a breadth-first-search (BFS) and augmenting path searching can be implemented efficiently (in terms of the number of queries) in [24] is that they show how to, for $S \in \cI$, $u \in S$, and $X \subseteq \bar{S}$, discover an element $x \in X$ with $(S \setminus \{u\}) \cup \{x\} \in \cI$ in $O(\log{n})$ rank queries using binary search (such a pair $(u,x)$ is called an exchange pair, and corresponds to an edge in the exchange graph).
The idea is that such an $x$ exists in $X$ if and only if $\rank((S \setminus \{u\}) \cup X) \geq |S|$.
Thus, we can do a binary search over $X$: we split $X$ into two equally-sized subsets $X_1$ and $X_2$, and check if such an $x$ exists in $X_1$ via the above equation. If it does, then we recurse on $X_1$ to find $x$. Otherwise, such an $x$ must exist in $X_2$ (as it does in $X$), and so we recurse on $X_2$.
To make this process efficient in our new model, we pre-build a binary search tree over the elements of $X$, where the internal nodes contain all the query-sets we need. That is, in the root node we have the query-set for $S\cup X$, and in its two children for $S\cup X_1$ respectively $S\cup X_2$.

Using this binary tree, one can simulate the binary search process as described above.
Since what we need to do in a BFS is to (i) find a replacement element $x$ and (ii) mark $x$ as visited (thus effectively “deactivate” $x$ in $X$), each time we see $x$, we just need to remove $x$ from the $O(\log{n})$ nodes on a root-to-leaf path, and thus the whole BFS algorithm runs in near-linear time as well.

Batching, Periodic Rebuilding, and Augmenting Sets.
The above binary search tree is efficient when the common independent set $S$ is static. However, once we find an augmenting path, we need to update $S$. This means that every node in the binary search tree needs to be updated.
If done naively, this would need at least $\Omega(nr)$ time, as there are up to $r$ augmentations, and rebuilding the tree takes $O(n)$ time.
Therefore, we employ a batching approach here.
That is, we do not walk through every node and update them immediately when we see an update to $S$.
Instead, we batch $k$ updates (for $k$ to be decided later) and pay an additional $O(k)$-factor every time we want to do a query in our tree. In other words, at some point, we might want to search for exchanges for a common independent set $S'$ (by doing queries like $(S' \setminus \{u\}) \cup X$ to find edges incident to $u$). Our binary tree might only have an outdated version $S$ (i.e. store sets like $S\cup X$). Then the cost of converting $S\cup X$ to $(S'\setminus \{u\}) \cup X$ is $|S\oplus S'| + 1$, which we assert is less than $k$.
When this number exceeds $k$, we rebuild the binary search tree completely using the up-to-date $S'$ instead, in $\tO(n)$ time.

Over the whole run of the algorithm, there are only $O(r \log r)$ updates to our common independent set $S$ (see, e.g., [26, 67]).
Hence, the total running time becomes

\[ \underbrace{\tO(nk\epsilon^{-1})}_{\text{Blocking-flow for $\tO(\epsilon^{-1})$ iterations}} + \underbrace{\tO(\epsilon rn)}_{\text{Remaining $\tO(\epsilon r)$ augmenting paths}} + \underbrace{\tO(nrk^{-1})}_{\text{Rebuilding binary search trees}}, \]

which is $\tO(nr^{2/3})$ for $k = r^{1/3}$ and $\epsilon =r^{-1/3}$.

To achieve the $\tO(n\sqrt{r})$ bound in our dynamic-rank-oracle model, there is one additional observation we need.
By the “Augmenting Sets” argument [24], for each element $v$ that we want to query our tree, it suffices to consider changes to $S$ that are in the same distance layer as $v$ is (in a single blocking-flow phase).
Since changes to $S$ are uniformly distributed among layers, when the $(s, t)$-distance in $G(S)$ is $d$, we only need to spend an additional $O(\frac{k}{d})$-factor (instead of an $O(k)$-factor) when querying the binary search tree.
This brings our complexity down to

\[ \tO\left(n\epsilon^{-1} + \sum_{d = 1}^{1/\epsilon}\frac{nk}{d}\right) + \tO(\epsilon rn) + \tO(nrk^{-1}), \]

where the first part is a harmonic sum which makes for $\tO(n\epsilon^{-1} + nk)$, and the total running time is $\tO(n\sqrt{r})$ for $k = r^{1/2}$ and $\epsilon = r^{-1/2}$.

§.§ Matroid Union

For simplicity of the presentation in this overview, let's assume we are solving the $k$-fold matroid union problem and that $k$—the number of bases[As an example, consider the problem of finding $k$ disjoint spanning trees of a graph.] we want to find—is constant.
A standard black-box reduction from matroid intersection, combined with our algorithm outlined above, immediately gives us an $\tO(n\sqrt{r})$ bound in the dynamic-rank-oracle model.
Nevertheless, we show how to exploit certain properties of matroid union to speed this up to $\tO(n + r\sqrt{r})$, i.e. near-linear time for sufficiently “dense”[We call matroids with $n \gg r$ “dense” by analogy to the graphic matroids where $n$ denotes the number of edges and $r$ the number of vertices.] matroids.

Suppose $\cM = (\ground,\cI)$ is the matroid we want to find $k$ disjoint bases for. The standard reduction to matroid intersection is that we create $k$ copies of all elements $u\in \ground$. Then we define two matroids as follows:

* The first matroid $\cM_1$ says that we only want to use one version of each element $u\in \ground$. We set $\cM_1 = (U\times \{1,\ldots,k\}, \cI_\text{part})$ to be the partition matroid defined as $S\in \cI_{\text{part}}$ if and only if $|\{(u,i)\in S : i = x\}| \le 1$ for all $x$.

* The second matroid $\cM_2$ says that for each copy of the ground set $\ground$ we must pick an independent set according to $\cM$. That is set $\cM_2 = (U\times \{1,\ldots,k\},\hat{\cI})$ to be the disjoint $k$-fold union of $\cM$, i.e. $S\in \hat{\cI}$ if and only if $\{u : (u,i)\in S\}$ is independent in $\cM$ for all $i$.

For a set $S$ which can be partitioned into $k$ disjoint independent sets, notice that in the exchange graph, the number of elements not in the first layer is bounded by $O(r)$.
This is because every $u\in \ground$ who is not represented in $S$ will be in the first layer $L_1$ of the BFS tree.
As such, we can build the BFS layers starting from the second layer if we can identify all the elements in this second layer.
This can be done by checking for each $y$ not in the first layer whether $L_1$ contains an exchange element of $y$ (via computing the rank of $(S \setminus \{y\}) \cup L_1$; no need to do a binary search).
Although binary search is not needed when identifying elements in the second layer, when going backward among layers to find an augmenting path $P$, we still have to find the exact element in the first layer which can be the first element of $P$ since it will decide which augmenting paths remain “compatible” later.
This inspires us to maintain two separate binary search trees: one, of size $O(r)$, for finding edges from the second layer and onward, and the other, of size $O(n)$, for finding the first elements of the augmenting paths.
Still, doing a binary search for each element in the first layer results in a total number of $O(r\epsilon^{-1})$ queries to the binary search tree, which is too much.
To reduce the number of queries down to $\tO(r)$, we note that only binary searches which correspond to the actual augmenting paths will succeed, i.e., reach the leaf nodes of the binary search tree.
Since there are at most $O(r/d)$ augmenting paths when the $(s, t)$-distance in $G(S)$ is $d$, we only need to do $O(r/d)$ queries to the binary search tree; other queries can be blocked by first checking if their corresponding exchange elements exist in the first layer.
This results in a running time of $\tO(n + r\sqrt{n})$ (note: $\sqrt{n}$ and not $\sqrt{r}$), which already matches Gabow's algorithm for $k$-disjoint spanning tree [45].

Toward $\tO(n + r\sqrt{r})$ for Matroid Union.
The bottleneck of the above algorithm is that we need to do binary searches over (and hence rebuild periodically) the tree data structure for the first layer (of size $\Omega(n)$).
If we can reduce the size of this tree down to $O(r)$, then the running time would be $\tO(n + r\sqrt{r})$.
This suggests that we might want to somehow “sparsify” the first layer.
Indeed, for a single augmenting path, we only need a basis of the first layer.
As a concrete example, consider the case of a graphic matroid: Given a forest $S$, an edge $e \in S$, and the set of non-tree edges $E \setminus S$, we want to find a “replacement” edge $e^\prime$ in $E \setminus S$ for $e$ which “restores” the connectivity of $S - e + e^\prime$.
In this case, it suffices to only consider a spanning forest (i.e. “basis”) $B$ of $E \setminus S$, in the sense that such a replacement edge exists in $E \setminus S$ if and only if it exists in this spanning forest $B \subseteq E\setminus S$.

Moreover, note that after each augmentation a single element will be removed from the first layer.
Thus, if we can maintain a decremental basis of the first layer, we can build our binary search tree data structure dynamically on top of this basis and get the desired time bound.

Maintaining a Basis in a Matroid.
Our data structure for maintaining a basis is inspired by the dynamic minimum spanning tree algorithm of [35], in combination with the sparsification trick of [34]. It uses $\tO(n)$ time to initialize, and then $\tO(\sqrt{r})$ dynamic rank queries[In the application of our matroid union algorithm, there will only be $\tO(r)$ updates, so this is efficient enough for our final $\tO(n+r\sqrt{r})$ algorithm.] per deletion.
It also supports maintaining a min-weight basis.

Let $L \subseteq \ground$ for $|L| = O(n)$ be the first layer in which we want to maintain a dynamic basis.
In the preprocessing stage, we split $L$ into $\sqrt{n}$ blocks $L_1, L_2, \ldots, L_{\sqrt{n}}$ of size roughly $\sqrt{n}$ and compute the basis of $L$ from left to right.
We also build the “prefix sums” of these $\sqrt{n}$ blocks so that we can quickly access/query sets of the form $L_1 \cup L_2 \cup \cdots \cup L_k$ for all values of $k$.
When we remove an element $x$ from $L_i$, we first update the prefix sums in $O(\sqrt{n})$ time.
If $x$ is not in the basis we currently maintain, then nothing additional needs to be done.
Otherwise, we have to find the “first” replacement element, which is guaranteed to be located in blocks $L_i, \ldots, L_{\sqrt{n}}$.
The block $L_j$ in which the replacement element lies can be identified simply by inspecting the ranks of the prefix sums, and after that, we then go through elements in that block to find the exact element.
Note that blocks after $L_j$ need not be updated, as for them it does not matter what basis we picked among blocks $L_1$ to $L_j$.
This gives us an $O(\sqrt{n})$-update time algorithm for maintaining a basis of a matroid.

To get a complexity of $O(\sqrt{r}\log n)$, we show that a similar sparsification structure as that of [34] for dynamic graph algorithms also works for arbitrary matroids. The sparsification is a balanced binary tree over the $n$ elements, where in each node we have an instance of our (un-sparsified) underlying data structure to maintain a basis consisting of elements in the subtree rooted at the node. Only elements part of the basis of a node are propagated upwards to the parent node. This means that in each instance of our underlying data structure we work over a ground set of size at most $2r$.
Thus, each update corresponds to at most two updates (a single insertion and deletion) to at most $O(\log n)$ (which is the height of the tree) nodes of the tree, each costing $O(\sqrt{r})$ dynamic rank queries in order to maintain the basis at this node.
This results in the desired time bound.

§ PRELIMINARIES

We use standard set notation.
In addition to that, for two sets $X$ and $Y$, we use $X + Y$ to denote $X \cup Y$ (when $X \cap Y = \emptyset$) and $X - Y$ to denote $X \setminus Y$ (when $Y \subseteq X$).
For an element $v$, $X + v$ and $X - v$ refer to $X + \{v\}$ and $X - \{v\}$, respectively.
Let $X \oplus Y$ denote the symmetric difference of $X$ and $Y$.

In this paper, we use the standard notion of matroids which is defined as follows.

A matroid $\cM = (\ground, \cI)$ is defined by a tuple consisting of a finite ground set $\ground$ and a non-empty family of independent sets $\cI \subseteq 2^\ground$ such that the following properties hold.

* Downward closure: If $S \in \cI$, then any subset $S^\prime \subseteq S$ is also in $\cI$.

* Exchange property: For any two sets $S_1, S_2 \in \cI$ with $|S_1| < |S_2|$, there exists an $x \in S_2 \setminus S_1$ such that $S_1 + x \in \cI$.

Let $\ground$ be the ground set of a matroid $\cM$.
For $S \subseteq \ground$, let $\bar{S}$ denote $\ground \setminus S$.
For $X \subseteq \ground$, the rank of $X$, denoted by $\rank(X)$, is the size of the largest independent set contained in $X$, i.e., $\rank(X) = \max_{S \in \cI}|X \cap S|$.
The rank of a matroid $\cM = (\ground, \cI)$ is the rank of $\ground$.
We let $r \leq n$ denote the rank of the input matriods.
When the input consists of more than one matroid (e.g., in the matroid union problem), let $\rank_i$ denote the rank function of the $\ith$ matroid.
A basis of $X$ is an independent set $S \subseteq X$ with $|S| = \rank(X)$.
A basis of $\cM$ is a basis of $\ground$.
A circuit is a minimal dependent set.
The span of $X$ contains elements whose addition to $X$ does not increase the rank of it, i.e., $\sspan(X) = \{u \in \ground \mid \rank(X \cup \{u\}) = \rank(X)\}$.

The rank function is submodular.
That is, $\rank(X) + \rank(Y) \geq \rank(X \cap Y) + \rank(X \cup Y)$ holds for each $X, Y \subseteq \ground$.

[see, e.g., <cit.>]
$\rank(A) = \rank(\sspan(A))$ holds for every $A \subseteq \ground$.

For two sets $X, Y$ and their bases $S_X, S_Y$, it holds that $\rank(S_X + S_Y) = \rank(X + Y)$.

Since $X, Y \subseteq \sspan(S_X + S_Y)$, we have $S_X + S_Y \subseteq X + Y \subseteq \sspan(S_X + S_Y)$.
The lemma then follows from $\rank(S_X + S_Y) = \rank(\sspan(S_X + S_Y))$ using <ref>.

Exchange Graph.
Our algorithms for matroid intersection and union will be heavily based on finding augmenting paths in exchange graphs.

For two matroids $\cM_1 = (\ground, \cI_1)$ and $\cM_2 = (\ground, \cI_2)$ over the same ground set and an $S \in \cI_1 \cap \cI_2$, the exchange graph with respect to $S$ is a directed bipartite graph $G(S) = (\ground \cup \{s, t\}, E_S)$ with $s, t \not\in \ground$ being two distinguished vertices and $E_S = E_1 \cup E_2 \cup E_s \cup E_t$, where

\begin{align*}
E_1 &= \{(x, y) \mid x \in S, y \not\in S,\;\text{and}\;S - x + y \in \cI_1\}, \\
E_2 &= \{(y, x) \mid x \in S, y \not\in S,\;\text{and}\;S - x + y \in \cI_2\}, \\
E_s &= \{(s, x) \mid S + x \in \cI_1 \},\;\text{and} \\
E_t &= \{(x, t) \mid S + x \in \cI_2 \}.
\end{align*}

The distance layers of $G(S)$ is the sets $L_1, \ldots, L_{d_{G(S)}(s, t) - 1}$, where $L_\ell$ consists of elements in $\ground$ that are of distance $\ell$ from $s$ in $G(S)$.
Most matroid intersection algorithms including ours are based on augmenting a common independent set with an augmenting path in $G(S)$ until such a path does not exist.
The following lemma certifies the correctness of this approach.

Let $P$ be a shortest $(s, t)$-path[In fact, $P$ only needs to be “chordless” [17], i.e., without shortcuts. Nonetheless, a shortest $(s, t)$-path suffices for our rank-query algorithms.] of $G(S)$.
Then, the set $S^\prime := S \oplus (V(P) \setminus \{s, t\})$ is a common independent set with $|S^\prime| = |S| + 1$.
On the other hand, if $t$ is unreachable from $s$ in $G(S)$, then $S$ is a largest common independent set.

We write $S \oplus P$, where $P$ is an augmenting path in $G(S)$, for the common independent set $S^\prime := S \oplus (V(P) \setminus \{s, t\})$ obtained by augmenting $S$ along $P$.
Let $d_{G(S)}(u, v)$ denote the $(u, v)$-distance in $G(S)$.
When $S$ is clear from context, let $d_t$ denote $d_{G(S)}(s, t)$.
The following lemma states that if $d_{G(S)}(s, t)$ is large, then $S$ is close to being optimal.

If $S \in \cI_1 \cap \cI_2$ satisfies $d_{G(S)}(s, t) \geq d$, then $|S|$ is at least $\left(1 - O(\frac{1}{d})\right)r$.

The following bound on the total length of shortest augmenting paths will be useful for our analysis.

If we solve matroid intersection by repeatedly finding the shortest augmenting paths, then the sum of the lengths of these augmenting paths is $O(r\log r)$.

If we augment along a shortest $(s, t)$-path in $G(S)$ to obtain $S^\prime$, then for each $u \in \ground$, the following hold (let $d := d_{G(S)}$ and $d^\prime := d_{G(S^\prime)})$.

* If $d(s, u) < d(s, t)$, then $d^\prime(s, u) \geq d(s, u)$. Similarly, if $d(u, t) < d(s, t)$, then $d^\prime(u, t) \geq d(u, t)$.

* If $d(s, u) \geq d(s, t)$, then $d^\prime(s, u) \geq d^\prime(s, t)$. Similarly, if $d(u, t) \geq d(s, t)$, then $d^\prime(u, t) \geq d^\prime(s, t)$.

Augmenting Sets.
The following notion of augmenting sets, introduced by [24], models a collection of “mutually compatible” augmenting paths, i.e., paths that can be augmented sequentially without interfering with each other.

Let $S \in \cI_1 \cap \cI_2$ satisfy $d_{G(S)}(s, t) = d_t$ and let $L_1, L_2, \ldots, L_{d_t - 1}$ be the distance layers of $G(S)$.
A collection $\Pi := (D_1, D_2, \cdots, D_{d_t - 1})$ is an augmenting set in $G(S)$ if

* $D_\ell \subseteq L_\ell$ holds for each $1 \leq \ell < d_t$,

* $|D_1| = |D_2| = \cdots = |D_{d_t - 1}|$,

* $S + D_1 \in \cI_1$,

* $S + D_{d_t - 1} \in \cI_2$,

* $S - D_\ell + D_{\ell + 1} \in \cI_1$ holds for each even $1 \leq \ell < d_t - 1$, and

* $S - D_{\ell + 1} + D_{\ell} \in \cI_2$ holds for each odd $1 \leq \ell < d_t - 1$.

One can think of the concept of augmenting sets as a generalization of augmenting paths.
Indeed, an augmenting path is an augmenting set where $|D_1| = \cdots = |D_{d_t - 1}| = 1$.
The term “mutually compatible” augmenting paths is formalized as follows.

A collection of vertex-disjoint shortest $(s, t)$-paths $\cP = (P_1, \ldots, P_k)$ in $G(S)$ is a collection of consecutive shortest paths if $P_i$ is a shortest augmenting path in $G(S \oplus P_1 \oplus \cdots \oplus P_{i - 1})$ for each $1 \leq i \leq k$.

The following structural lemmas of [24] will be useful for us, particularly in deriving <ref> in <ref>.

Let $\Pi := (D_1, \ldots, D_{d_t - 1})$ be an augmenting set in $G(S)$.
Then, $S^\prime := S \oplus \Pi := S \oplus D_1 \oplus \cdots \oplus D_{d_t - 1}$ is a common independent set.

For two augmenting sets $\Pi = (D_1, \ldots, D_{d_t - 1})$ and $\Pi^\prime = (D_1^\prime, \ldots, D_{d_t - 1}^\prime)$, we use $\Pi \subseteq \Pi^\prime$ to denote that $D_{\ell} \subseteq D_{\ell}^\prime$ hold for each $1 \leq \ell < d_t$.
In this case, let $\Pi^\prime \setminus \Pi := (D_1^\prime \setminus D_1, \ldots, D_{d_t - 1}^\prime \setminus D_{d_t - 1})$.
We will hereafter abuse notation and let $\Pi$ also denote the set of elements $D_1 \cup \cdots \cup D_{d_t - 1}$ in it.
In particular, $\ground \setminus \Pi$ denotes $\ground \setminus \left(D_1 \cup \cdots \cup D_{d_t - 1}\right)$.

For two augmenting sets $\Pi \subseteq \Pi^\prime$ in $G(S)$, $\Pi^\prime \setminus \Pi$ is an augmenting set in $G(S \oplus \Pi)$.

Given a collection of consecutive shortest paths $P_1, \ldots, P_k$ in $G(S)$, where $P_i = (s, a_{i,1}, \ldots, a_{i, d_t - 1}, t)$, the collection $\Pi = (D_1, \ldots, D_{d_t - 1})$, where $D_i = \{a_{1,i}, \ldots, a_{k, i}\}$, is an augmenting set in $G(S)$.

The converse of <ref> also holds.

Given an augmenting set $\Pi$ in $G(S)$, there is a collection consecutive shortest paths $P_1, \ldots, P_k$ in $G(S)$ where $P_i = (s, a_{i,1}, \ldots, a_{i,d_t - 1}, t)$ such that $D_i = \{a_{1,i}, \ldots, a_{k,i}\}$.

Note that <ref> are not equivalent to the exact statements of <cit.> (in particular, they did not specify how $\Pi$ and $P_i$ are constructed), but our versions are clear from their proof.

Let $S \in \cI_1 \cap \cI_2$ with $d_{G(S)}(s, t) = d_t$ and $\Pi \subseteq \Pi^\prime$ be two augmenting sets in $G(S)$.
Let $u \not\in \Pi^\prime$ be an element.
If $u$ is not on any augmenting path of length $d_t$ in $G(S \oplus \Pi)$, then $u$ is not on any augmenting path of length $d_t$ in $G(S \oplus \Pi^\prime)$ either.

Let $S^\prime := S \oplus \Pi$ and $S^{\prime\prime} := S \oplus \Pi^\prime$.
Since $S^{\prime\prime}$ can be obtained by augmenting $S^\prime$ along a series of shortest augmenting paths (by <ref>), the claim follows from the fact that the $(s, u)$-distance and $(u, t)$-distance are monotonic (<ref>).

Let $\Pi = (D_1, \ldots, D_{d_t - 1})$ be an augmenting set in $G(S)$ and $P = (s, a_1, \ldots, a_{d_t - 1}, t)$ be an augmenting path in $G(S \oplus \Pi)$.
Then, $\Pi^\prime = (D_1 + a_1, \ldots, D_{d_t - 1} + a_{d_t - 1})$ is an augmenting set in $G(S)$.

This directly follows from <ref>.

Using Dynamic Oracle.
In the following sections except for <ref> where we discuss independence-query algorithms, all algorithms and data structures will run in the dynamic-rank-oracle model (see <ref>).
In other words, we will simply write “in $t$ time” for “in $t$ time and dynamic rank queries”.
We will use the term query-sets to refer to the sets $S_i$ in <ref>.
In particular, constructing a query-set means building the corresponding set from $S_0 = \emptyset$ with the $\textsc{Insert}(\cdot)$ operation.
Insertion/Deletion of an element into/from a query-set is done via the $\textsc{Insert}$/$\textsc{Delete}$ operations.
Using the $\textsc{Query}$ operation, we assume that we know the ranks of all the query-sets we construct in our algorithms.

§ BINARY SEARCH TREE

In this section, we give the core data structure of our algorithms which allows us to do binary searches and find free elements (elements $x$ such that $S + x \in \cI$) and exchange pairs (pairs $(x,y)$ such that $S-x+y\in \cI$, corresponding to edges in the exchange graph) efficiently.
We also support updating the common independent set $S$ that the exchange relationship is based upon.
For a matroid $\cM = (\ground, \cI)$, the data structure has the following guarantee ($s, t \not\in U$ denote the two distinguished vertices of the exchange graph as defined in <ref>).

For any integer $\beta \geq 1$, there exists a data structure that supports the following operations.

* $\textsc{Initialize}(\cM, S, Q_S, X)$: Given $S \in \cI$, the query-set $Q_S$ that corresponds to $S$, and $X \subseteq \bar{S}$ (respectively, $X \subseteq S$ or $X = \{t\}$), initialize the data structure in $\tO(|X|)$ time. The data structure also maintains $S$.

* $\textsc{Find}(y)$: Given $y \in S \cup \{s\}$ (respectively, $y \in \bar{S}$),

* if $y \in S$ (respectively, $X \subseteq S$), then return an $x \in X$ such that $S - y + x \in \cI$ (respectively, $S - x + y \in \cI$), or

* if $y = s$ (respectively, $X = \{t\}$), then return an $x \in X$ such that $S + x \in \cI$ (respectively, return the only element $x = s$ or $x = t$ in $X$ if $S + y \in \cI$ and $\bot$ otherwise).

The procedure returns $\bot$ if such an $x$ does not exist.
The procedure takes $\tO(\beta)$ time if the result is not $\bot$, and $\tO(1)$ time otherwise.

* $\textsc{Delete}(x)$: Given $x \in X$, if $x \not\in \{s, t\}$, delete $x$ from $X$ in $O(\log{n})$ time.

* $\textsc{Replace}(x, y)$: Given $x \in X$ and $y \not\in X$, replace $x$ in $X$ by $y$ in $O(\log{n})$ time.

* $\textsc{Update}(\Delta)$: Update $S$ to $S \oplus (\Delta \setminus \{s, t\})$ in amortized $\tO(\frac{|X| \cdot |\Delta|}{\beta})$ time.

To make sense of the seemingly complicated input and casework of <ref>, one should focus on the first item of $\textsc{Find}(\cdot)$.
We will use <ref> to explore the exchange graphs, and thus we need to find an exchange element $x$ of $y$ as in the first case.
The additional complication is included solely because we also have to deal with edges incident to $s$ or $t$.
For instance, say $X \subseteq \bar{S}$, then $\textsc{Find}(s)$ finds an edge in $G(S)$ directed from $s$ to $X$.
This will make our algorithms presented later cleaner (see <ref> for example).

Sometimes, we will omit the $Q_S$ parameter of $\textsc{Initialize}$, meaning that we explicitly build the query-set $Q_S$ from $S$ in $O(r)$ time before running the actual initialization.
In such cases, $|X|$ will be $\Omega(r)$, and thus this incurs no overhead.

We will later refer to the case of $X \subseteq \bar{S}$ as the co-circuit binary search tree and the case of $X \subseteq S$ as the circuit binary search tree.
The data structure follows from the binary search algorithm of <cit.>, which is based on the following observation.

To find free elements and exchange pairs, we can use the following observations.

Free element:
There exists an $x \in X$ such that $S + x \in \cI$ if and only if $\rank(S + X) > |S|$.

Co-circuit exchange:
Given $y\in S$, there exists an $x \in X$ such that $S - y + x \in \cI$ if and only if $\rank(S - y + X) \geq |S|$.

Circuit exchange:
Given $y\not\in S$,
there exists an $x \in X$ such that $S - x + y \in \cI$ if and only if $\rank(S - X + y) = |S-X+y|$.

The data structure of <ref> is built upon the following similar data structure whose independent set $S$ is “static” in the sense that its update will be specified for each query.
We construct the data structure of <ref> first, and then use it for <ref> in <ref>.

There exists a data structure that supports the following operations.

* $\textsc{Initialize}(\cM, S, Q_S, X)$: Given $S \in \cI$, a query-set $Q_S$ corresponding to $S$, and $X \subseteq \bar{S}$ (respectively, $X \subseteq S$ or $X = \{t\}$), initialize the data structure in $\tO(|X|)$ time.

* $\textsc{Find}(y)$: Let $S^\prime := S \oplus \Delta$. It is guaranteed that $S^\prime \in \cI$. Given $y \in S^\prime \cup \{s\}$ (respectively, $y \in \bar{S^\prime}$),

* if $y \in S^\prime$ (respectively, $X \subseteq S^\prime$), then return an $x \in X$ such that $S^\prime - y + x \in \cI$ (respectively, $S^\prime - x + y \in \cI$), otherwise

* if $y = s$ (respectively, $X = \{t\}$), then return an $x \in X$ such that $S^\prime + x \in \cI$ (respectively, return the only element $x = s$ or $x = t$ in $X$ if $S^\prime + y \in \cI$ and $\bot$ otherwise),

in $\tO(\beta)$ time.
The procedure returns $\bot$ if such an $x$ does not exist.

* $\textsc{Delete}(x)$: Given $x \in X$, delete $x$ from $X$ in $O(\log{n})$ time.

* $\textsc{Replace}(x, y)$: Given $x \in X$ and $y \not\in X$, replace $x$ by $y$ in $X$ in $O(\log{n})$ time.

We present the co-circuit version of the data structures as the circuit version is analogous (their difference is essentially stated in the two cases <ref> and <ref> of <ref>).
The data structure of <ref> is a balanced binary tree in which every node $v$ corresponds to a subset $X_v$ of $X$.
The subsets correspond to nodes at the same level form a disjoint partition of $X$.
There are $|X|$ leaf nodes, each of which corresponds to a single-element subset of $X$.
An internal node $v$ with children $u_1$ and $u_2$ has $X_v = X_{u_1} \sqcup X_{u_2}$.
Each node $v$ is also associated with a query-set $Q_v := S + X_v$, for which we have prepared a dynamic oracle (see <ref>).

In the initialization stage, we first compute the query-set of the root node $Q_r := S + X$ from $Q_S$ in $O(|X|)$ time.
As long as the current node $v$ has $|X_v| > 1$, we split $X_v$ into two equally-sized subsets $X_{u_1}, X_{u_2}$, compute $Q_{u_1}, Q_{u_2}$ from $Q_v$, and then recurse on the two newly created nodes $u_1$ and $u_2$.
Computing $Q_{u_1}$ and $Q_{u_2}$ from $Q_v$ takes $O(|X_v|)$ time in total, and thus the overall running time for initialization is $\tO(|X|)$.

To find an exchange element of $y \in S^\prime$, we perform a binary search on the tree.
For each node $v$, we can test whether such an element exists in $X_v$ via <ref><ref> by computing the query-set $Q^\prime_v := S^\prime - y + X_v$ from $Q_v := S + X_v$ in $1+|\Delta|$ dynamic-oracle queries.
If such an element does not exist for the root $X_r = X$, then we return $\bot$.
Otherwise, for node $v$ initially being $r$, there must exist one of the child nodes $u_i$ of $v$ where such an exchange $x$ exists in $X_{u_i}$.
We then recurse on $u_i$ until we reach a leaf node, at which point we simply return the corresponding element.
Similarly, to find a free element, we compute the rank of $Q^\prime_v := S^\prime + X_v$ instead (see <ref><ref>).
Since we need to compute $Q^\prime_v$ for each of the visited nodes, the running time is $O(|\Delta|\log{n})$.

For deletion of $x$, we simply walk up from the leaf node corresponding to $x$ to the root node and remove $x$ from each of the $X_v$ and $Q_v$.
This takes time proportional to the depth of the tree, which is $O(\log{n})$.
Replacement of $x$ by $y$ follows similarly from deletion of $x$: instead of simply removing $x$ from $X_v$ and $Q_v$, we add $y$ to them as well.

Note that the above binary search tree is static in the sense that we only deactivate elements from a fixed initial set.
We can extend this data structure to support a dynamically changing input set $X$ by using a dynamic binary search tree based on partial rebuilding [10, 11] instead.
The amortized time complexity remains the same since rebuilding a subtree takes time proportional to the number of nodes of it.

§.§ Periodic Rebuilding

Here we extend <ref> to prove <ref>. Recall that the difference between the two data structures is that we need to support a dynamically changing independent set in <ref> (which we will need since $S$ changes after each augmentation in our matroid algorithms).
How we achieve this is to essentially employ a batch-and-rebuild approach to the binary search tree of <ref>.

We maintain a binary search tree $\cT := \textsc{Initialize}(\cM, S, Q_S, X)$ of <ref> and a collection of “batched” updates $\tilde{\Delta}$ of size at most $\beta$.
Throughout the updates, we also maintain the query-set corresponding to the current $S$ starting from the given $Q_S$ and the query-set corresponding to $S + X$, which initially can be computed from $Q_S$ in $O(|X|)$ time.
Each call to $\textsc{Find}(y)$ is delegated to $\cT.\textsc{Find}(y, \tilde{\Delta})$, which runs in time $\tO(|\tilde{\Delta}|) = \tO(\beta)$ time.
Note that we can test whether the result of $\cT.\textsc{Find}(\cdot)$ will be $\bot$ in $\tO(1)$ time by simply checking if <ref><ref> (or <ref> if $y = s$) holds with the query-set corresponding to $S + X$ we maintain.

Each call to $\textsc{Delete}(x)$ and $\textsc{Replace}(x, y)$ translates simply to $\cT.\textsc{Delete}(x)$ and $\cT.\textsc{Replace}(x, y)$.
For an update to $S$ with $\Delta$, we set $\tilde{\Delta} \gets \tilde{\Delta} \cup \Delta$ and update $S$ and the query-sets accordingly.
If the size of $\tilde{\Delta}$ exceeds $B$, then we rebuild the binary search tree with the input common independent set being the up-to-date $S$ we maintain.
Note that we will pass query-set $Q_S$ to $\textsc{Initialize}$ to not pay the extra $O(r)$ factor.
Finally, since the binary search tree is now up-to-date, we set $\tilde{\Delta}$ to be $\emptyset$.
The rebuilding takes $\tO(|X|)$ time and is amortized to $\tO(\frac{|X| \cdot |\Delta|}{\beta})$ per update operation with $|\Delta|$ changes.

§ MATROID INTERSECTION

In this section, we present a matroid intersection algorithm in the dynamic-rank-oracle model that matches the state-of-the-art algorithm [24] in the traditional model.

For two matroids $\cM_1 = (\ground, \cI_1)$ and $\cM_2 = (\ground, \cI_2)$, it takes $\tO(n\sqrt{r})$ time to obtain the largest $S \in \cI_1 \cap \cI_2$ in the dynamic-rank-oracle model.

The algorithm follows the blocking-flow framework of [24] similar to the Hopcroft-Karp algorithm for bipartite matching [49], which goes as follows.
Initially, they start with $S = \emptyset$.

*  First, they obtain a common independent set that is of size at least $(1 - \epsilon)r$ by eliminating all augmenting paths of length $O(1/\epsilon)$. In each of the $O(1/\epsilon)$ iterations, they first compute the distance layers of $G(S)$ along which they find a maximal set of compatible shortest augmenting paths using an approach similar to a depth-first-search from $s$.
Augmenting paths are searched in a depth-first-search manner.
Whenever an element has no out-edge with respect to the current common independent set to the next layer, they argue that it can be safely removed as it will not be on a shortest augmenting path anymore in this iteration.
Augmenting along these augmenting paths increases the $(s, t)$-distance of $G(S)$ by at least one.

*  With the current solution which is only $\epsilon$ fraction away from being optimal, they find the remaining $O(\epsilon r)$ augmenting paths one at a time.

A proper choice of $\epsilon$ (in this case it is $\epsilon = 1/\sqrt{r}$) that balances the cost between the two steps results in their algorithm.

§.§ Building Distance Layers

Building distance layers and finding a single augmenting path in Step <ref> is immediate by replacing binary searches in <cit.> with the binary search trees of <ref>.

It takes $\tO(n)$ time to compute the $(s, u)$-distance for each $u \in \ground$ and find the shortest $(s, t)$-path in $G(S)$ or determine that $t$ is unreachable from $s$.

First, we build two binary search trees via <ref> with $\beta = 1$, a circuit binary search tree $\T_1 := \textsc{Initialize}(\cM_1, S, X_1)$ where $X_1 = S$ for the first matroid and a co-circuit binary search tree $\T_2 := \textsc{Initialize}(\cM_2, S, X_2)$ where $X_2 = \bar{S}$ for the second matroid. Initializing these takes $\tO(n)$ time.
These two binary search trees allow us to explore the exchange graph efficiently.

Then we run the usual BFS algorithm from the source $s$ (or equivalently, all $u \in \bar{S}$ with $S + u \in \cI_1$).
For each visited element $u$, if $u \in S$, then we repeatedly find $x \in X_2$ such that $S - u + x \in \cI_2$ using $\T_2.\textsc{Find}(u)$, mark $x$ as visited, and remove $x$ from $X_2$ via $\T_2.\textsc{Delete}(x)$ (until $\bot$ is returned).
Similarly, for $u \in \bar{S}$, we find $x \in X_1$ with $S - x + u \in \cI_1$, mark $x$ as visited, and remove $x$ from $X_1$ using $\T_1$.
This explores all the unvisited out-neighbors of $u$ in $G(S)$.
Since each element will be visited at most once, the total running time is $\tO(n)$.

§.§ Blocking Flow

In this section, we prove the following lemma regarding a single phase of blocking-flow computation.

Given an $S \in \cI_1 \cap \cI_2$ with $d_{G(S)}(s, t) = d$, it takes $\tO\left(n + \frac{n\sqrt{r}}{d} + \frac{(|S^\prime| - |S|) \cdot nd}{\sqrt{r}}\right)$ time to obtain an $S^\prime \in \cI_1 \cap \cI_2$ with $d_{G(S^\prime)}(s, t) > d_{G(S)}(s, t)$.

Before proceeding to prove <ref>, we first use it to finish our matroid intersection algorithm.
Like Hopcroft-Karp bipartite matching algorithm [49] and the matroid intersection algorithm of [24], we run several iterations of blocking-flow, and then keep augmenting until we get the optimal solution.

Starting from $S = \emptyset$, we run the blocking-flow algorithm until $d_{G(S)}(s,t) \geq \sqrt{r}$.
This, by <ref>, takes

\begin{equation}
\tO\left(n\sqrt{r}\right) + \tO\left(\sum_{d = 1}^{\sqrt{r}}\frac{n\sqrt{r}}{d}\right) + \tO\left(\frac{n}{\sqrt{r}}\cdot\left(\sum_{d = 1}^{\sqrt{r}}{d \cdot (|S_d| - |S_{d - 1}|)}\right)\right)
\label{eq:timebound}
\end{equation}

time, where $S_d$ is the size of the $S$ we get after augmenting along paths of length $d$.
Observe that $\sum_{d = 1}^{\sqrt{r}}{d \cdot (|S_d| - |S_{d - 1}|)}$ is the sum of lengths of the augmenting paths that we use, and thus the third term in <ref> is $\tO(\frac{n}{\sqrt{r}} \cdot r) = \tO(n\sqrt{r})$ by <ref>.
The second term also sums up to $\tO(n\sqrt{r})$ (by a harmonic sum), and therefore the total running time of the blocking-flow phases is $\tO(n\sqrt{r})$.
The current common independent set $S$ has size at least $r - O(\sqrt{r})$ by <ref>, and thus finding the remaining $O(\sqrt{r})$ augmenting paths one at a time takes a total running time of $\tO(n\sqrt{r})$ via <ref>.
This concludes the proof of <ref>.

The rest of the section is to prove <ref>.
Our blocking-flow algorithm is a slight modification to <cit.>, as shown in <ref>.
It takes advantage of the data structure of <ref> to explore an out-edge from the current element $a_{\ell}$ to $A_{\ell + 1}$—the set of “alive” elements in the next layers—while (approximately) keeping track of the current common independent set $S$.
An element $u$ is “alive” if it has not been included in the augmenting set $\Pi := (D_1, \ldots, D_{d_t - 1})$ yet, nor has the algorithm determines that there cannot be any shortest augmenting path through $u$.

Blocking flow

$S \in \cI_1 \cap \cI_2$
$S^\prime \in \cI_1 \cap \cI_2$ with $d_{G(S^\prime)}(s, t) > d_{G(S)}(s, t)$

Build the distance layers $L_1, \ldots, L_{d_t - 1}$ of $G(S)$ with <ref>
$L_0 \gets \{s\}$ and $L_{d_t} \gets \{t\}$
$A_\ell \gets L_{\ell}$ for each $0 \leq \ell \leq d_t$
$\cT_{\ell} \gets \textsc{Initialize}(\cM_{1}, S, Q_S, L_{\ell})$ for each odd $1 \leq \ell \leq d_t$ by <ref> with $\beta = \sqrt{r} / d$
$\cT_{\ell} \gets \textsc{Initialize}(\cM_{2}, S, Q_S, L_{\ell})$ for each even $1 \leq \ell \leq d_t$ by <ref> with $\beta = \sqrt{r} / d$
$\ell \gets 0$, $a_0 \gets s$, and $D_{\ell} \gets \emptyset$ for each $1 \leq \ell < d_t$
$\ell \geq 0$
$\ell < d_t$
$A_{\ell} = \emptyset$

$a_{\ell + 1} \gets \cT_{\ell + 1}.\textsc{Find}(a_\ell)$
$a_{\ell + 1} = \bot$
$A_\ell \gets A_\ell - a_\ell$ and $\ell \gets \ell - 1$

$\ell \gets \ell + 1$

Found augmenting path $a_1, a_2, \ldots a_\ell$
$i \in \{1, 2, \ldots, d_t - 1\}$
$D_{i} \gets D_{i} + a_{i}$ and $A_{i} \gets A_{i} - a_{i}$
$\cT_{i}.\textsc{Delete}(a_i)$ and $\cT_{i}.\textsc{Update}(\{a_{i - 1}, a_{i}\})$

$\ell \gets 0$

return $S^\prime := S \oplus \Pi$, where $\Pi := (D_1, D_2, \ldots, D_{d_t - 1})$

We emphasize that the difference between <ref> and <cit.> is exactly in the replacement of binary searches with the data structure of <ref>.
Note that indeed by the specification stated in <ref>, the binary search trees let us explore edges in the exchange graph (see <ref>).
As a result, our proof will focus on showing that such a replacement does not affect the correctness.
For this, we need the concept of augmenting sets (see <ref>) which characterizes a collection of “mutually compatible” augmenting paths—i.e. a “blocking flow”.
The structural results in <ref> culminate in the following lemma that is key to the correctness of our algorithm.
It models when we can safely “remove” an element since there will be no augmenting path through it in the future.
This is in particular required for us (as opposed to the simpler argument used in [24]) because the set $S$ is not fully updated after each augmentation (at least in the binary search trees that we use to explore the exchange graphs).

Let $\Pi \subseteq \Pi^\prime$ be augmenting sets in $G(S)$ with distance layers $L_1, \ldots, L_{d_t - 1}$ where $d_{G(S)}(s, t) = d_t$.
For $x \in L_\ell$, if there is no $y \in L_{\ell + 1}$ such that

\begin{equation}
(S \oplus D_{\ell} \oplus D_{\ell + 1}) \oplus \{x, y\} \in \cI,\;\text{where $\cI := \cI_1$ if $\ell$ is even and $\cI := \cI_2$ if $\ell$ is odd},
\label{eq:condition}
\end{equation}

then there is no augmenting path of length $d_t$ through $x$ in $G(S \oplus \Pi^\prime)$.

We claim that there is no augmenting path of length $d_t$ through $x$ in $G(S \oplus \Pi)$: If there is such a $P$, then we can put $P$ into $\Pi$ and get an augmenting set $\tilde{\Pi} := (\tilde{D}_1, \ldots, \tilde{D}_{d_t - 1})$ by <ref>.
By definition of the augmenting set, this means that there is such a $y \in \tilde{D}_{k + 1} \setminus D_{k + 1}$ satisfying (<ref>), a contradiction to our assumption.
The lemma now follows from <ref>.

We are now ready to prove <Ref>.

We analyze the running time of <ref> first.
Similar to <cit.>, in each iteration, we use $\cT_\ell.\textsc{Find}(\cdot)$ to find an out-edge of $a_{\ell}$, taking $\tO(\beta) = \tO(\sqrt{r}/d)$ time by <ref>.
In each iteration, we either increase $\ell$ and extend the current path by a new element, decrease $\ell$ and remove one element, or find an $(s, t)$-path (then remove everything in it), and each element can participate in each of the event at most once.
Thus, there are only $O(n)$ iterations, and the total cost of $\cT_{\ell}.\textsc{Find}(\cdot)$ is consequently $\tO(\frac{n\sqrt{r}}{d})$ by our choice of $\beta$.
For each of the augmenting path, $\cT_{\ell}.\textsc{Update}(\cdot)$ takes $\tO\left(\frac{|L_\ell| \cdot d}{\sqrt{r}}\right)$ time, contributing to a total running time of $\tO\left(\frac{(|S^\prime| - |S|) \cdot nd}{\sqrt{r}}\right)$ since $L_\ell$'s are disjoint.

We then argue the correctness of the algorithm.
Observe that at any point in time, $\cT_\ell$ is a data structure capable of finding a replacement element with respect to the independent set $S \oplus D_{\ell - 1} \oplus D_\ell$, due to the updates that we gave it.
This means that the collection $\Pi := (D_1, D_2, \ldots, D_{d_t - 1})$ remains an augmenting set in $G(S)$ because $S \oplus (D_{\ell - 1} + a_{\ell - 1}) \oplus (D_{\ell} + a_\ell)$ is independent for each $\ell$ whenever a path is found.
As a result, when the algorithm terminates, $S^\prime := S \oplus \Pi$ is indeed a common independent set as guaranteed by <ref>.

It remains to show that $d_{G(S^\prime)}(s, t) > d_{G(S)}(s, t)$ by arguing that for each $a_{\ell}$ not in $\Pi$ but removed from $A_{\ell}$ at time $t$, there is no shortest augmenting path in $G(S^\prime)$ that passes through $a_{\ell}$.
This is a direct consequence of <ref> since $\Pi^{(t)}$, the augmenting set obtained at time $t$, is contained in $\Pi$.
The fact that $\cT_{\ell + 1}^{(t)}.\textsc{Find}(a_{\ell})$ returns nothing (equivalently, <ref> is not satisfied) shows that $a_{\ell}$ is not on any shortest augmenting path in $G(S^\prime)$ since the set $X$ maintained in $\cT_{\ell + 1}^{(t)}$ (see <ref>) is $A_{\ell + 1}$ at all time.
We remark that $x$ might have an out-edge (with respect to $S \oplus D_{\ell}^{(t)} \oplus D_{\ell}^{(t + 1)}$) to a removed element with distance $\ell + 1$ from $s$ (not in $A_{\ell + 1}$), but such an element, by induction, is not on any augmenting path either.

§ DYNAMICALLY MAINTAINING A BASIS OF A MATROID

In this section, we construct a data structure that allows us to maintain a basis of a matroid in a decremental set.
The data structure is used for obtaining an $\tO_k(n + r\sqrt{r})$ running time for matroid union, but it may be of independent interest as well.
Specifically, our data structure has the following guarantees.

For a (weighted) matroid $\cM = (U, \cI)$, there exists a data structure supporting the following operations.

* $\textsc{Initialize}(X)$: Given a set $X \subseteq U$, initialize the data structure and return a (min-weight) basis $S$ of $X$ in $\tO(n)$ time.

* $\textsc{Delete}(x)$: Given $x \in X$, remove $x$ from $X$ and return a new (min-weight) basis of $X$ in $\tO(\sqrt{r})$ time. Specifically, the new basis will contain at most one element (the replacement element of $x$) not in the old basis, and this procedure returns such an element if any.

Our data structure for <ref> will consist of two parts.
The first part, introduced in <ref>, is a baseline, unsparsified data structure that supports the $\textsc{Delete}$ operation in $\tO(\sqrt{n})$ time, and the second one is a sparsification structure which brings the complexity down to $\tO(\sqrt{r})$, as presented in <ref>.

As hinted by the statement of <ref>, to make things simpler, we will assign an arbitrary but unique weight $w(x)$ to each $x \in X$.
Now, instead of maintaining an arbitrary basis of $X$, we maintain the min-weight basis instead.
The min-weight basis is well-known to be unique (as long as the weights are) and can be obtained greedily as shown in <ref> (see, e.g., [31]).

Greedy algorithm for computing the min-weight basis

A set $X \subseteq U$ of size $k$
The min-weight basis $S$ of $X$
Order $X = (x_1, x_2, \ldots, x_{k})$ so that $w(x_1) < w(x_2) < \cdots < w(x_{k})$
$S \gets \emptyset$
$i \in [1, k]$
$\rank(S + x_i) > \rank(S)$
$S \gets S + x_i$

return $S$

Moreover, suppose we remove $x \in S$ from the set $X$. Then the new min-weight basis is either
(i) $S - x + y$ where $y$ is the minimum weight element in $X - x$ that makes $S - x + y$ independent or
(ii) simply $S - x$ if such a $y$ does not exist.
In case (i), $y$ is called the replacement element of $x$.
Note that $w(y) > w(x)$ must hold.

It is useful to note that the $S$ in Line <ref> of <ref> is interchangeable with $X_{i - 1} = \{x_1, \ldots, x_{i - 1}\}$, since
$\sspan(X_{i - 1}) = \sspan(S \cap X_{i - 1})$, so the sets $X_{i-1}$ and $S\cap X_{i-1}$ have the same rank.
In other words, in each iteration $i$, we can imagine that <ref> has chosen every element before $x_i$.

In <ref>, $x_i \in S$ if and only if $\rank(X_{i}) > \rank(X_{i - 1})$.

§.§ Baseline Data Structure

Our baseline data structure supports the operations of <ref>, except in time $\tO(\sqrt{k})$ where $k = |X|$ instead of $\tO(\sqrt{r})$.

For a weighted matroid $\cM = (U, \cI)$, there exists a data structure supporting the following operations.

* $\textsc{Initialize}(X)$: Given a set $X \subseteq U$ with $|X| = k$, initialize the data structure and return the min-weight basis $S$ of $X$ in $\tO(k)$ time.

* $\textsc{Delete}(x)$: Given $x \in X$, remove $x$ from $X$ and return the new min-weight basis of $X$ in $\tO(\sqrt{k})$ time. Specifically, the new basis will contain at most one element (the replacement element of $x$) not in the old basis, and this procedure returns such an element if any.

* $\textsc{Insert}(x)$: Given $x \not\in X$, add $x$ to $X$. It's guaranteed that $x$ is not in the min-weight basis of the new $X$ and the size of $X$ does not exceed $2k$.

In the initialization stage, we order $X$ by the weights and split the sequence into $\sqrt{k}$ blocks $X_1, X_2, \ldots, X_{\sqrt{k}}$ from left to right, where each block has roughly the same size $O(\sqrt{k})$.
That is, $X_1$ contains the $\sqrt{k}$ elements with the smallest weights while $X_{\sqrt{k}}$ contains elements with the largest weights.
We also compute the basis $S$ of $X$ from left to right as in <ref> together with $\sqrt{k}$ query-sets $Q_1, Q_2, \ldots, Q_{\sqrt{k}}$, where $Q_j = \bigcup_{i = 1}^{j}X_i$ is the union of the first $j$ blocks.
This takes $\tO(k)$ time in total.

For each deletion of $x$ located in the block $X_i$, we first update the query-sets $Q_i, \ldots, Q_{\sqrt{k}}$ by removing $x$ from them.
Let $Q_1^\prime, \ldots, Q_{\sqrt{k}}^\prime$ denote the old query-sets before removing $x$.
If $x$ is not in the basis $S$ we currently maintain, then $S$ remains the min-weight basis of the new $X$ and nothing further needs to be done.
Otherwise, we would like to find the min-weight replacement element $y$ of $x$.
We know that such a $y$, if it exists, can only be located in blocks $X_i, X_{i + 1}, \ldots, X_{\sqrt{k}}$.
As such, we find the first $j \geq i$ with $\rank(Q_j) = \rank(Q_j^\prime)$ and recompute the portion of $S$ inside $X_j$.
This can be done by running <ref> with the initial set $S$ being $Q_{i - 1}$, the union of the first $i - 1$ blocks (see <ref>).
Thus, the deletion takes $\tO(\sqrt{k})$ time.

For insertion of $x$, we simply add $x$ to a block where it belongs (according to $w(x)$) and then update $Q_i$'s appropriately.
This takes $\tO(\sqrt{k})$ as well.

To maintain an update time of $\tO(\sqrt{k})$, whenever the size of a block $X_i$ grows larger than $2\sqrt{k}$, we split it into two blocks and recompute $Q_i$ and $Q_{i+1}$.
Similarly, to avoid having too many blocks, whenever the size of a block $X_i$ goes below $\sqrt{k} / 2$, we merge it with an adjacent block and remove $Q_i$.
Each of the above operations takes $\tO(\sqrt{k})$ time, which is subsumed by the cost of an update.

We have shown how to implement each operation of <ref> in its desired running time, and the correctness of the data structure is manifest as we always follow the greedy basis algorithm (<ref>).

§.§ Sparsification

In this section, we prove <ref> by “sparsifying” the input set of the data structure for <ref> in a recursive manner, similar to what [34] did to improve [35]'s $O(\sqrt{|E|})$ dynamic MST algorithm to $O(\sqrt{|V|})$.
The following claim asserts that such sparsification is valid.

Let $S_X$ and $S_Y$ be the min-weight basis of $X$ and $Y$, respectively, where $w(x) < w(y)$ holds for each $x \in X$ and $y \in Y$.
Then, the min-weight basis of $S_X + S_Y$ is also the min-weight basis of $X + Y$.

Consider running the greedy <ref> on the set $X + Y$ to obtain the min-weight basis $S$ of it.
Clearly, we have $S_X \subseteq S$ since $X$ contains the elements of smaller weights (in fact $S \cap X = S_X$).
Assume for contradiction that $S \cap Y \not\subseteq S_Y$, i.e., there exists a $y^{*} \in S \cap Y$ which does not belong to $S_Y$.
Then, it must be the case that there exists a $y \in S_Y$ with $w(y) > w(y^{*})$, as otherwise (i.e., $y^{*}$ is ordered after everything in $S_Y$) by <ref> the greedy algorithm stops before seeing $y^{*}$.
We claim that the greedy algorithm on $Y$ chooses $y^{*}$ before all such $y$'s, thereby contradicting the fact that $S_Y$ is the min-weight basis of $Y$.
This is true by the diminishing returns property[The diminishing returns property of submodular functions states that $f(z+X)-f(X) \geq f(z+Y)-f(Y)$ holds for each $Y \subseteq X \subseteq \ground$ and $z \not\in X$.] of the rank function: Let $Y^{*}$ be elements in $Y$ with weights smaller than $w(y^{*})$.
Since $y^{*} \in S$, it follows that $\rank(X + Y^{*} + y^{*}) > \rank(X + Y^{*})$, implying $\rank(Y^{*} + y^{*}) > \rank(Y^{*})$ and the greedy algorithm run on $Y$ picks $y^{*}$.

We are now ready to present our sparsification data structure.

Our data structure is a balanced binary tree where the leaf nodes correspond to elements in $X$ and each internal node corresponds to the set consisting of elements in leaf nodes of this subtree.
We will abuse notation and use a node $v$ to also refer to the elements contained in the subtree rooted at $v$.

We first build the binary tree top-down, starting with the root node containing $X$ and recursively splitting the current set into two subsets of roughly the same size and recursing on them.[Note that unlike in <ref>, we are not building query-sets here.]
We then build the min-weight basis of each node in a bottom-up manner, starting from the leaves.
For each node $v$ with children $u_1$ and $u_2$, we initialize the data structure $\cD_v$ for <ref> with input set $S_{u_1} + S_{u_2}$, the min-weight basis of $u_1$ and $u_2$ which are obtained from $\cD_{u_1}$ and $\cD_{u_2}$.
By <ref>, the basis $\cD_v$ maintains is the min-weight basis of $v$.
Thus, by induction, the basis maintained in the root node is indeed the min-weight basis of the whole set $X$.
The data structure for <ref> takes time near-linear in the size of the input set to construct, and since the sparsified input is a subset of elements in the subtree, the initialization takes time near-linear in the sum of sizes of the subtrees, which is $\tO(n)$ (indeed, every element occurs in at most $\log n$ nodes).

To delete an element $x \in X$, we first identify the leaf node $v_x$ of the binary tree which corresponds to $x$.
Going upward, for each ancestor $p$ of $v_x$, we delete $x$ from $\cD_p$.
If we find a replacement element $y$ for $x$, we insert $y$ into $\cD_{q}$, where $q$ is $p$'s parent, before proceeding to $q$ ($y$ is not in $\cD_p$ so such an insertion is valid by <ref>).
Since $x$ will be removed from $\cD_q$ shortly, the input set of $\cD_q$ remains the union of the min-weight bases of $q$'s children.
This takes $\tO(\sqrt{r})$ time since $\cD_p$ is of size $O(r)$.
Inductively, since the min-weight bases of the child nodes are updated, by <ref>, the min-weight basis of each of the affect nodes (hence the min-weight basis of $X$) is correctly maintained.

§ MATROID UNION

In this section, we present our improved algorithm for matroid union.
Our main focus of this algorithm is on optimizing the $O(n\sqrt{r})$ term to $O(r\sqrt{r})$.
Thus, for simplicity of presentation, we will treat $k$ as a constant (the dependence on $k$ will be a small polynomial) and express our bounds using the $O_k(\cdot)$ and $\tO_k(\cdot)$ notation.

In the dynamic-rank-oracle model, given $k$ matroids $\cM_i = (U_i, \cI_i)$ for $1 \leq i \leq k$, it takes $\tO_k(n + r\sqrt{r})$ time to find a basis $S \subseteq U_1 \cup \cdots \cup U_k$ of $\cM = \cM_1 \vee \cdots \vee \cM_k$ together with a partition $S_1, \ldots, S_k$ of $S$ in which $S_i \in \cI_i$ for each $1 \leq i \leq k$.

In <ref>, we present an optimized (for the parameter $k$) version of the above algorithm which solves the important special case when all the $k$ matroids are the same—i.e. $k$-fold matroid union—with applications in matroid packing problems. For example, the problem of finding $k$ disjoint spanning trees in a graph falls under this special case. In particular, in <ref>, we obtain the following <ref>, and we discuss some immediate consequences for the matroid packing, matroid covering, and $k$-disjoint spanning trees problems in <ref>.

In the dynamic-rank-oracle model, given a matroid $\cM = (U, \cI)$ and an integer $k$, it takes $\tO(n + kr\sqrt{\min(n, kr)} + k\min(n, kr))$ time to find the largest $S \subseteq U$ and a partition $S_1, \ldots, S_k$ of $S$ in which $S_i \in \cI$ for each $1 \leq i \leq k$.

The rest of this section will focus on the proof of
<ref> (again, where the number of matroids $k$ is treated as a constant).
Our algorithm is based on the matroid intersection algorithm in <ref>, in which we identify and optimize several components that lead to the improved time bound.

§.§ Reduction to Matroid Intersection

For completeness, we provide a standard reduction from matroid union to matroid intersection.
For an in-depth discussion, see <cit.>.
Let $\cM_i = (U_i, \cI_i)$ be the given $k$ matroids and $U = U_1 \cup \cdots \cup U_k$ be the ground set of the matroid union $\cM = \cM_1 \vee \cdots \vee \cM_k$.
We first relabel each element in the matroids with an identifier of its matroid, resulting in $\hat{\cM}_i = (\hat{U}_i, \cI_i)$, where $\hat{U}_i = \{(u, i) \mid u \in U_i\}$.
Let $\hat{\cM} = (\hat{U}, \hat{\cI}) = \hat{\cM}_1 \vee \cdots \vee \hat{\cM}_k$ be over the ground set $\hat{U} = \hat{U}_1 \sqcup \cdots \sqcup \hat{U}_k$.

In other words, in $\hat{\cM}$, we duplicate each element that is shared among multiple matroids into copies that are considered different, effectively making the ground sets of the $k$ matroids disjoint.
After this modification, an independent set in $\hat{\cM}$ is now simply the union of $k$ independent sets, one from each matroid.
However, that might not be what we want since these independent sets may overlap, i.e., contain copies that correspond to the same element.
We therefore intersection $\hat{\cM}$ with a partition matroid $\cM_{\text{part}} = (\hat{U}, \cI_{\text{part}})$ given by

\[ \cI_{\text{part}} = \{S \subseteq \hat{U} \mid \left|S \cap \{(u, i)\;\text{for $1 \leq i \leq k$} \mid u \in U_i\}\right| \leq 1\;\text{holds for each $u \in U$} \} \]

to restrict different copies of the same element to be chosen at most once.
The matroid union problem is thus reducible to the matroid intersection problem in the sense that the intersection of $\hat{\cM}$ and $\cM_{\text{part}}$ maps exactly to the independent sets of the matroid union $\cM$.

Notation-wise, given the above mapping between the two worlds, whenever we write $S \in \cI_{\text{part}} \cap \hat{\cI}$, a subset set of $\hat{U}$, we will equivalently regard $S$ as a subset of $U$ with an implicit partition $S_1, \ldots, S_k$ where $S_i \in \cI_i$.

§.§ Specialized Matroid Intersection Algorithm

Given the reduction, to prove <ref>, it suffices to compute the intersection of $\hat{\cM}$ and $\cM_{\text{part}}$ in the claimed time bound.
In the following, we will set $\cM_1$ to be $\cM_{\text{part}}$ and $\cM_2$ to be $\hat{\cM}$ when talking about exchange graphs and other data structures.
Our main goal is to optimize the $O(n\sqrt{r})$ term to $O(r\sqrt{r})$, so it might be more intuitive to think of $r \ll n$.
We first show that for an $S \in \cI_\text{part} \cap \hat{\cI}$, the exchange graph $G(S)$ is quite unbalanced in the sense that most elements appear in the first distance layer.
In fact, the first distance layer of $G(S)$ contains all duplicates of elements $u$ in $U$ that do not appear in $S$.
This is by definition of $G(S)$ and the fact that $\cM_1 = \cM_{\text{part}}$ is the partition matroid.
In the following, when the context is clear, we let $d_t$ denote the $(s, t)$-distance of $G(S)$ and $L_1, \ldots, L_{d_t - 1}$ denote the distance layers.

It holds that $L_1 = \{(u, i) \mid (u, i) \in \hat{U}\;\text{and}\;(u, j) \not\in S\;\text{for any $1 \leq j \leq k$}\}$.

Similarly, the odd layers of $G(S)$ (that corresponds to $\bar{S}$) are well-structured in the sense that they consist of elements whose one of the duplicates appears in $S$.
By definition of $G(S)$, we also know that elements in odd layers have only a single in-edge, which is from their corresponding duplicate in $S$.
These elements thus all have the same distance from $s$.

It holds that $L_3 \cup L_5 \cup \cdots \cup L_{d_t - 1} = \{(u, i) \mid (u, i) \in \hat{U}\;\text{and}\;(u, j) \in S\;\text{for some}\;i \neq j\}$,
and for each $(u, i) \in L_3 \cup \cdots \cup L_{d_t - 1}$, we have $d_{G(S)}(s, (u, i)) = d_{G(S)}(s, (u, j)) + 1$ where $(u, j) \in S$.

Union Exchange Graph. Given the above facts, we introduce another notion of exchange graphs which is commonly used for matroid union (see, e.g., [32, 26]).
For the given $k$ matroids $\cM_i = (U_i, \cI_i)$ and a subset $S \subseteq U$ that can be partitioned into $k$ independent sets $S_1, \ldots, S_k$ with $S_i \in \cI_i$, the union exchange graph is a directed graph $H(S) = (U \cup \{s, t\}, E)$ with two distinguished vertices $s, t \not\in U$ and edge set $E = E_s \cup E_t \cup E_{\text{ex}}$, where

\begin{align*}
E_s &= \{(s, u) \mid u \not\in S\}, \\
E_t &= \{(u, t) \mid S_i + u \in \cI_i\;\text{for some $1 \leq i \leq k$}\},\;\text{and} \\
E_{\text{ex}} &= \{(u, v) \mid S_i - v + u \in \cI_i\;\text{where $v \in S_i$}\}. \\
\end{align*}

We can see that the exchange graph $G(S)$ with respect to $S \in \cI_{\text{part}} \cap \hat{\cI}$ (as a subset of $\hat{U}$) and the union exchange graph $H(S)$ with respect to $S \subseteq U$ is essentially the same in the sense that $H(S)$ can be obtained from $G(S)$ by contracting all copies of the same element in the first layers and skipping all other odd layers.
In particular, for each $(u, i) \in S$, in $G(S)$, there might be a direct edge from $(u, i)$ to $(u, j)$ and an edge from $(u, j)$ to $(v, j)$, where $(v, j) \in S_j$ and $S_j - v + u \in \cI_j$.
Correspondingly, in $H(S)$, we skip the intermediate vertex $(u, j)$ and meld the above two edges as one direct edge from $u \in S_i$ to $v \in S_j$.
We also merge all edges from $s$ to some $(u, i)$ of the same $u$ in the first layer to a single edge from $s$ to $u$ (<ref>).
This simplification does not impact the distance layers of $H(S)$ since all such $(u, j)$ have the same distance from $s$ (<ref>).

From now on, for simplicity, our algorithms will run on the union exchange graphs $H(S)$, i.e., we will perform blocking-flow computation and augment $S$ along paths in $H(S)$.
On the other hand, to not repeat and specialize all the lemmas to the case of union exchange graphs, proofs and correctness will be argued implicitly in the perspective of the exchange graph $G(S)$ for matroid intersection.
For instance, for $P = (s, a_1, \ldots, a_{d_t - 1}, t)$ a shortest $(s, t)$-path in $H(S)$, “augmenting $S$ along $P$” means moving $a_i$ to the independent set that originally contains $a_{i + 1}$ for each $i \geq 1$, and thus effectively enlarge the size of $S$ by one via putting $a_1$ in it.[One can show that the matroid union $\cM$ is a matroid <cit.>. As such, a basis can be obtained by trying to include each element into $S$. From the union exchange graph perspective, the independence test of $S + x$ corresponds to asking whether “there is a path in $H(S)$ from $x$ to $t$”.]
One can verify that this is indeed what happens if we map $P$ back to a path $P^\prime$ in $G(S)$, and then perform the augmentation of $S$ (as a subset of $\hat{U}$) along $P^\prime$.

Our main idea to speed up the matroid union algorithm to $\tO_k(r\sqrt r)$ (instead of $\tO_k(n \sqrt{r})$) is to “sparsify” the first layer of $H(S)$ by only considering a subset of elements contained in some basis.  We formalize this in the following <ref> together with <ref>.

Given $S \in \cI_\text{part} \cap \hat{\cI}$ and $k$ bases $\{B_i\}_{i = 1}^{k}$ of $U_i \setminus S$, it takes $\tO_k(r)$ time to construct the distance layers $L_2, \ldots, L_{d_t - 1}$ of $H(S)$.

Note that we know exactly what elements are in the first distance layer, so computing $L_2, \ldots, L_{d_t - 1}$ suffices.

BFS in a union exchange graph

$S \subseteq U$ which partitions into $S_1, \ldots, S_k$ of independent sets and $k$ bases $\{B_i\}_{i = 1}^{k}$ of $U_i \setminus S$
The $(s, u)$-distance $d(u)$ in $H(S)$ for each $u \in S \cup \{t\}$

$\mathsf{queue} \gets B_1 \cup \cdots \cup B_k$
$d(u) \gets \infty$ for each $u \in S \cup \{t\}$, and $d(u) \gets 1$ for each $u \in B_1 \cup \cdots \cup B_k$
$\cT_i \gets \textsc{Initialize}(\cM_i, S_i, S_i)$ (<ref> with $\beta = 1$)
$\mathsf{queue} \neq \emptyset$
$u \gets \mathsf{queue}.\textsc{Pop}()$
$i \in \{1, 2, \ldots, k\}$ where $u \in U_i$ and $u \not\in S_i$
$v := \cT_i.\textsc{Find}(u) \neq \bot$
$d(v) \gets d(u) + 1$ and $\mathsf{queue}.\textsc{Push}(v)$

$S_i + u \in \cI$ and $d(t) = \infty$
$d(t) \gets d(u) + 1$

return $d(u)$ for each $u \in S \cup \{t\}$

The algorithm is presented as <ref>, and it is essentially a breadth-first-search (BFS) starting from $B_1 \cup \cdots \cup B_k$ instead of $s$.
Out-edges in $H(S)$ are explored via $k$ binary search trees $\cT_1, \cT_2, \ldots, \cT_k$ of <ref>, one for each matroid $\cM_i$ and independent set $S_i$.
Let's analyze the running time first.
Building $\cT_i$ takes a total of $\tO(|S|) = \tO_k(r)$ time.
Exploring the graph takes $\tO(|S \cup B_1 \cup \cdots \cup B_k| \cdot k) = \tO_k(r)$ time in total since each element in $S$ is found at most once by $\cT_i.\textsc{Find}(\cdot)$ because $S_i$'s are disjoint, and we also spend $O(k)$ time for each element in $S \cup B_1 \cup \cdots \cup B_k$ iterating over $\cT_i$.

It remains to show that starting from $B_1 \cup \cdots \cup B_k$ instead of $U \setminus S$ does not affect the correctness of the BFS.
For this, it suffices to show that we successfully compute $d(u)$ for all $u \in S$ with distance $2$ from $s$.
By definition, $u \in S_i$ is of distance $2$ from $s$ if and only if there exists an $x \in U_i \setminus S$ such that $S_i - u + x \in \cI_i$.
This is equivalent to $\rank_i(S_i - u + (U_i \setminus S)) > \rank_i(S_i)$ by <ref>.
But then by <ref>, we have $\rank_i(S_i - u + (U_i \setminus S)) = \rank_i(S_i - u + B_i)$, and so such an $x$ exists in $B_i$ as well.
This concludes the proof of <ref>.

Given an $S \in \cI_{\text{part}} \cap \hat{\cI}$ with $d_{H(S)}(s, t) = d_t$ together with data structures $\cD_i$ of <ref> that maintains a basis of $U_i \setminus S$ for each $1 \leq i \leq k$, it takes $\tO_k(r + \frac{r\sqrt{r}}{d_t} + (|S^\prime| - |S|) \cdot d_t\sqrt{r})$ time to obtain an $S^\prime \in \cI_{\text{part}} \cap \hat{\cI}$ with $d_{H}(S^\prime)(s, t) > d_t$, with an additional guarantee that $\cD_i$ now maintains a basis of $U_i \setminus S^\prime$ for each $1 \leq i \leq k$.

Blocking flow in a union exchange graph

$S \subseteq U$ which partitions into $S_1, \ldots, S_k$ of independent sets and a dynamic-basis data structure $\cD_i$ of $U_i \setminus S$ for each $1 \leq i \leq k$
$S^\prime \in \cI_{\text{part}} \cap \cI_k$ with $d_{H(S^\prime)}(s, t) > d_{H(S)}(s, t)$
$\cD_i$ maintains a basis of $U_i \setminus S^\prime$ at the end of the algorithm for each $1 \leq i \leq k$

Build the distance layers $L_2, \ldots, L_{d_t - 1}$ of $H(S)$ with <ref>
$L_0 \gets \{s\}$ and $L_{d_t} \gets \{t\}$
$B_i \gets$ the basis maintained by $\cD_i$ and $L_1 \gets B_1 \cup \cdots \cup B_k$
$A_\ell \gets L_\ell$ for each $0 \leq \ell \leq d_t$
$\cT_{\ell}^{(i)} \gets \textsc{Initialize}(\cM_i, S_i, Q_{S_i}, A_{\ell} \cap S_i)$ for each $2 \leq \ell < d_t$ and $1 \leq i \leq k$ (<ref> with $\beta = \sqrt{r} / d_t$)
$D_{\ell} \gets \emptyset$ for each $1 \leq \ell < d_t$
$\ell \gets 0$ and $a_0 \gets s$
$\ell \geq 0$
$\ell < d_t$
$A_{\ell} = \emptyset$

$\ell = 0$
Find an $a_{\ell + 1} := \cT_{\ell + 1}^{(i)}.\textsc{Find}(a_\ell) \neq \bot$ for some $1 \leq i \leq k$

$a_{\ell + 1} \gets$ an arbitrary element in $A_1$

such an $a_{\ell + 1}$ does not exist
$\ell \geq 2$
$\cT_{\ell}^{(j)}.\textsc{Delete}(a_{\ell})$ where $a_{\ell} \in S_j$

$A_\ell \gets A_\ell - a_\ell$ and $\ell \gets \ell - 1$

$\ell \gets \ell + 1$

Found augmenting path $a_1, a_2, \ldots a_\ell$
$D_1 \gets D_1 + a_1$ and $A_1 \gets A_1 - a_1$
$i \in \{1, 2, \ldots, k\}$ where $a_1 \in U_i$
$B_i \gets B_i - a_1$
$\cD_i.\textsc{Delete}(a_1)$ returns a replacement $x$
$B_i \gets B_i + x$ and $A_1 \gets A_1 \cup \{x\}$

$i \in \{2, \ldots, d_t - 1\}$
$D_{i} \gets D_{i} + a_{i}$ and $A_{i} \gets A_{i} - a_{i}$
$\cT_{i}^{(j)}.\textsc{Delete}(a_i)$ and $\cT_{i}^{(j)}.\textsc{Update}(\{a_{i - 1}, a_{i}\})$ where $a_i \in S_j$

Augment $S$ along $P = (s, a_1, \ldots, a_{d_t - 1}, t)$
$\ell \gets 0$

return $S$

Our blocking-flow algorithm for matroid union is presented as <ref>.
As it is equivalent to <ref> running on $G(S)$ except that the first layer $L_1 := B_1 \cup \cdots \cup B_k$ is now only a subset (which is updated after each augmentation) of $\ground \setminus S$, we skip most parts of the proof and focus on discussing this difference.
That is, we need to show that if $A_1$ becomes empty, then there is no augmenting path of length $d_t$ in $H(S^\prime)$ anymore.
Given how $A_1$ and $B_i$'s are maintained and <ref> (note that the set $X$ maintained in $\cT_{\ell}^{(i)}$ is always $A_\ell \cap S_i$ with respect to the current $S_i$ and thus it lets us explore out-edges to $A_{\ell} \cap S_i$ satisfying <ref>), $A_1$ is always the subset of $B_1 \cup \cdots \cup B_k$ consisting of elements that still potentially admits augmenting path of length $d_t$ in $H(S^\prime)$ through them.
That means if $A_1 = \emptyset$, then there is no augmenting set of length $d_t$ in $G(S^\prime)$, that starts from some $b \in B_1 \cup \cdots \cup B_k$.
This would imply that there is no such path even if we start from $x \in (\ground_i \setminus S) \setminus D_1$ as $B_i$ is a basis of it: if $S_i + x - y \in \cI$ for some $x \in (\ground_i \setminus S) \setminus D_1$ and $y \in S_i$, then there is a $b \in B$ with $S + b - y \in \cI$, and thus a path starting from $x$ can be converted into a path starting from $b$.
On the other hand, all elements in $D_1$ are not on a such path by <ref> either.
This shows that indeed $d_{H(S^\prime)}(s, t) > d_{H(S)}(s, t)$.

The guarantee that $\cD_i$ now operates on $U_i \setminus S^\prime$ is clear: Augmenting along $P = (s, a_1, \ldots, a_{d_t - 1}, t)$ corresponds to adding $a_1$ into $S$, and since we call $\cD_i.\textsc{Delete}(a_1)$ in Line <ref> after each such augmentation, $\cD_i$ indeed stays up-to-date.

It remains to analyze the running time of <ref>.
Computing distance layers with <ref> takes $\tO_k(r)$ time.
The number of elements that have ever been in some $A_i$ is $O_k(r + |S^\prime| - |S|)$ since
(i) $L_2 \cup \cdots \cup L_{d_t - 1}$ has size $O_k(r)$,
(ii) the initial basis $B_i$ of $\ground_i \setminus S$ for each $1 \leq i \leq k$ has total size $O_k(r)$, and
(iii) each of the $|S^\prime| - |S|$ augmentations adds at most $O_k(1)$ elements to $A_1$.
Similar to <ref>, this means that there are at most $O_k(r)$ iterations, each taking $O_k(\frac{\sqrt{r}}{d_t})$ time in $\cT_{\ell + 1}^{(i)}.\textsc{Find}(\cdot)$ with our choice of $\beta$.
The algorithm found $|S^\prime| - |S|$ augmenting paths, taking $\tO_k(d_t\sqrt{r} \cdot (|S^\prime| - |S|))$ time in total to update the binary search trees.
Also, for each such augmentation, we need $\tO_k(\sqrt{r})$ time to update the basis $B_i$ for all $1 \leq i \leq k$, which is subsumed by the cost of updating $\cT_{i}^{(j)}$.
These components sum up the total running time of

\[ \tO_k\left(r + \frac{r\sqrt{r}}{d_t} + \left(|S^\prime| - |S|\right) \cdot d_t\sqrt{r}\right). \]

<ref> now follows easily.

We initialize the dynamic-basis data structure $\cD_i$ of <ref> on $\ground_i$ for each of the matroid $\cM_i$.
We then run <ref> for at most $\sqrt{r}$ iterations with $\{\cD_i\}_{i = 1}^{k}$ until $d_{H(S)}(s, t) \geq \sqrt{r}$ and get an $S \in \cI_{\text{part}} \cap \hat{\cI}$ with $\cD_i$ now operating on $\ground_i \setminus S$ for each $1 \leq i \leq k$.
This takes

\[ \tO_k\left(r\sqrt{r} + \sum_{d = 1}^{\sqrt{r}}\frac{r\sqrt{r}}{d} + \sum_{d = 1}^{\sqrt{r}}d \cdot \left(|S_d| - |S_{d - 1}|\right)\right) = \tO_k(r\sqrt{r})\]

By <ref>, $S$ is $O_k(\sqrt{r})$ steps away from being optimal, and thus we find the remaining augmenting paths one at a time using <ref> in $\tO_k(r\sqrt{r})$ time in total.
Note that since a single augmentation corresponds to adding an element to $S$ (hence removing it from $\ground \setminus S$), we can maintain the basis of $\ground_i \setminus S$ that <ref> needs in $\tO_k(\sqrt{r} \cdot \sqrt{r})$ total update time, which is subsumed by other parts of the algorithm.

§.§ Matroid Packing and Covering

A direct consequence of our matroid union algorithm (<ref> in particular) is that we can solve the following packing and covering problem efficiently.
As a reminder, the exact dependence on $k$ of our algorithm is $\tO(n + kr\sqrt{\min(n, kr)} + k \min(n, kr))$ by <ref>.

For a matroid $\cM = (\ground, \cI)$, it takes $\tO(n\sqrt{n} + \frac{n^2}{r})$ time to find the largest integer $k$ and a collection of disjoint subsets $\cS = \{S_1, S_2, \ldots, S_k\}$ of $\ground$ such that $S_i$ is a basis for each $1 \leq i \leq k$ under the dynamic-rank-query model.

It's obvious that $k \leq \frac{n}{r}$ holds.
We do a binary search of $k$ in the range $[0, \frac{n}{r}]$, and for each $k$, we can determine the largest subset $S$ of $\ground$ which can be partitioned into $k$ disjoint independent sets by <ref>.
If $|S| = kr$, then it means that there are at least $k$ disjoint bases.
Otherwise, there are less than $k$ disjoint bases.
The running time is $\tO(n\sqrt{n} + \frac{n^2}{r})$.

For a matroid $\cM = (\ground, \cI)$, it takes $\tO(\alpha r\sqrt{n} + \alpha n)$ time to find the smallest integer $\alpha$ and a partition $\cS = \{S_1, S_2, \ldots, S_\alpha\}$ of $\ground$ such that $S_i \in \cI$ holds for each $1 \leq i \leq \alpha$ under the dynamic-rank-query model.

We first obtain a $2$-approximation $\alpha^{\prime}$ of $\alpha$ (i.e., $\alpha \leq \alpha^\prime \leq 2\alpha$) by enumerating powers of $2$, running <ref> with $k = 2^i$, and checking if the returned $S$ has size $n$: If $|S| = n$, then we know $2^i$ independent sets suffice to cover $\ground$.
Note that the enumeration stops whenever we found a suitable value of $\alpha^\prime$.
The exact value of $\alpha$ can then be found by a binary search in $[\frac{\alpha^\prime}{2}, \alpha^\prime]$.
This takes $\tO(\alpha r\sqrt{n} + \alpha n)$ (note that $\alpha r \geq n$ must hold).

§.§ Application: Spanning Tree Packing

We demonstrate the applicability of our techniques by deriving an $\tO(|E| + (k|V|)^{3/2})$ algorithm for the $k$ disjoint spanning tree problem in a black-box manner.
This improves Gabow's specialized $\tO(k^{3/2}|V|\sqrt{|E|})$ algorithm [45].
Since all applications of our algorithms follow the same reduction, we only go through it once here.
Refer to <ref> for other applications of both our matroid union and matroid intersection algorithms.

Given an undirected graph $G = (V, E)$, it takes $\tO(|E| + (k|V|)^{3/2})$ time to find $k$ edge-disjoint spanning trees in $G$ or determine that such spanning trees do not exist with high probability[We use with high probability to denote with probability at least $1 - |V|^{-c}$ for an arbitrarily large constant $c$.].

By <ref>, it suffices to provide a data structure that supports the three dynamic-oracle operations (<ref>) in $\polylog(|V|)$ time.
Our black-box reduction makes use of the worst-case connectivity data structure of [52, 40], which can be adapted to in $O(\polylog(|V|))$ update time maintain the rank of a set of edges (see <ref> for a discussion on how this can be done).

Let $\cM_G$ be the graphic matroid with respect to $G = (V, E)$.
$G$ admits $k$ edge-disjoint spanning trees if and only if $\cM_G$ admits $k$ disjoint bases.
The theorem now follows from <ref> with $n = |E|$ and $r = |V| - 1$ since <ref> returns a union of $k$ disjoint bases if they exist (we note that $k \le |E|/(|V|-1) \le O(|V|)$, and hence the $O(k^2 r)$ term is dominated by the $O((kr)^{3/2})$ term).

§ SUPER-LINEAR QUERY LOWER BOUNDS

Lower bounds for matroid intersection have been notoriously difficult to prove. The current highest lower bound is due to Harvey [47] which says that $(\log_2 3) n - o(n)$ queries are necessary for any deterministic independence-query algorithm solving matroid intersection.
Obtaining an $\omega(n)$ lower bound has been called a challenging open question [24].

In this section, we show the first super-linear query lower bound for matroid intersection, both in our new dynamic-rank-oracle model (<ref>), and also for the traditional independence-oracle model, thus answering the above-mentioned open question and improving on the bounds of [48].
We obtain our lower bounds by studying the communication complexity for matroid intersection.

If Alice is given a matroid $\cM_1 = (\ground,\cI_1)$
and Bob a matroid $\cM_2 = (\ground,\cI_2)$, any deterministic communication protocol needs $\Omega(n \log n)$ bits of communication to solve the matroid intersection problem.

The communication lower bound of <ref> implies a similar lower bound for the number of independence queries needed.
We argue that any independence-query algorithm can be simulated by Alice and Bob in the communication setting by exchanging a single bit per query asked. Whenever they want to ask an independence query “Is $S \in \cI_{i}$?”, Alice or Bob will check this locally and share the answer with the other party by sending one bit of communication.

Unfortunately, this argument does not extend to the traditional rank-oracle model (since each rank query can in fact reveal $\Theta(\log n)$ bits of information, which need to be sent to the other party). However, for the new dynamic-rank-oracle model, the $\Omega(n\log n)$ lower bound holds as now each new query only reveals constant bits of information: either the rank remains the same, increases by one, or decreases by one (and Alice or Bob can send which is the case to the other party with a constant number of bits). Our discussion proves the following corollaries, given <ref>.

Any deterministic (traditional) independence-query algorithm solving matroid intersection requires $\Omega(n \log n)$ queries.

Any deterministic dynamic-rank-query algorithm solving matroid intersection requires $\Omega(n \log n)$ queries.

We note that our lower bounds are also valid for the matroid union problem, due to the standard reductions[See <ref> for a reduction from matroid union to matroid intersection. To reduce from matroid intersection to matroid union, consider $\cM = \cM_1 \vee \cM_2^{*}$, where $\cM_2^{*}$ is the dual matroid of $\cM_2$ ($S \subseteq U$ is independent in $\cM_2^{*}$ if and only if $U - S$ contains a basis). It's easy to show that the basis $B$ of $\cM$ in $\cM_1$ will be of the form $B = S \cup (U \setminus R)$, where $S$ is the solution to the intersection between $\cM_1$ and $\cM_2$ and $R$ is an arbitrary basis of $\cM_2$ that contains $S$.] between matroid intersection and union.

§.§ Communication Setting

We study the following communication game
which we call .
Alice and Bob are given matroids $\cM_1 = (\ground,\cI_1)$ respectively $\cM_2 = (\ground,\cI_2)$.
Suppose they are also both given a common independent set $S\in \cI_1\cap \cI_2$, and they wish to determine
whether $S$ is a maximum-cardinality independent
is an easier version of
the matroid intersection problem, as Alice and Bob can just ignore the candidate $S$.

Our idea is that in order to solve
, Alice and Bob need to determine if there exists an augmenting path—that is an $(s,t)$-path—in the exchange graph $G(S)$ (see <ref> and <ref>). It is known that  in a
graph requires $\Omega(n\log n)$ bits of communication (<ref>, [50]). Using strict gammoids as our matroids, we argue that we can choose exactly how the underlying exchange graph looks like, and hence that matroid intersection admits the same lower bound.

Let $H = (V,E)$ be a directed graph and $X\subseteq V$ a subset of vertices.
Then $(H,X)$ defines a matroid $\cM = (V,\cI)$ called a strict gammoid, where a set of vertices $Y\subseteq V$ is independent if and only if
there exists a set of vertex-disjoint directed paths (some of which might just consist of single vertices) in $H$ whose starting points all belong to $X$ and whose ending points are exactly $Y$.

Suppose $G=(L,R,E)$ is a directed bipartite graph and $a, b \in R$ are two unique vertices such that $a$ has zero in-degree and $b$ has zero out-degree.
Then there exist two matroids $\cM_1, \cM_2$ over the ground set $L\cup R$ such that
$L$ is independent in both matroids and
the exchange graph $G(L)$ is exactly $G$ plus two extra vertices ($s$ and $t$) and two extra edges ($s\to a$ and $b \to t$).

Let $F_{1} = \{(u,v) | (u,v)\in E, u\in L, v\in R\}$ be the directed edges from $L$ to $R$ in $G$,
$F_{2} = \{(u,v) | (v,u)\in E, u\in L, v\in R\}$ be the (reversed) directed edges from $R$ to $L$ in $G$.
Also let $H_1 = (L\cup R,F_1)$ and $H_2 = (L\cup R,F_2)$ be the directed graphs with these edges respectively.

We let $\cM_1$, respectively $\cM_2$, be the strict gammoids defined by $(H_1, L+a)$ respectively $(H_2, L+b)$. Now $L$ is independent in both matroids. It is straightforward to verify that the exchange graph $G(L)$ is exactly as described in the claim. We certify that this is the case for the edges defined by $\cM_1$ ($\cM_2$ is similar):

* $G(L)$ will have an edge from $s$ to $a$, since
$L+a$ is independent in $\cM_1$.
Additionally note that $a$ has in-degree zero in $G$ (and hence is an isolated vertex in $H_1$).

* For any $x\in L, y\in R$, the edge $(x,y)$ exists in $G(L)$
if and only if $L - x + y$ is independent in $\cM_1$. By definition this is if and only if there exists a vertex-disjoint path starting from $L$ and ending to $L-x+y$ in $H_1$, or equivalently if the edge $(x,y)$ exists in $H_1$ (indeed, all vertices in $L-x$ must be both starts and ends of paths, so the path to $y$ must have started in $x$).

We now proceed to reduce an instance of  to that of , which concludes the proof of <ref>.

Suppose $G = (V, E_A \cup E_B)$ is an undirected graphs on $n=|V|$ vertices,
where Alice knows edges $E_A$ and Bob knows edges $E_B$.
They are also both given vertices $s$ and $t$, and want to determine
if $s$ and $t$ are connected in $G$.

The deterministic communication complexity of
is $\Omega(n\log n)$.

We show that an instance of  can be converted to an instance
of  of roughly the same size.
Suppose the symbols are defined as in  Definition <ref>.
Let $\bar{V} = \{\bar{v} : v\in V\}$ be a copy of $V$.
We construct a directed bipartite graph $G' = (V, \bar{V}, E'_A \cup E'_B)$
as follows:

* $(v,\bar{v}) \in E'_A$ for all $v\in V$.

* $(\bar{v},v) \in E'_B$ for all $v\in V$.

* $(v,\bar{u}), (u,\bar{v}) \in E'_A$ for all $\{u,v\}\in E_A$.

* $(\bar{v},u), (\bar{u},v) \in E'_A$ for all $\{u,v\}\in E_B$.

* No other edges exist.

Alice knows $E'_A$, and Bob knows $E'_B$. $G'$ has $2n$ vertices and $2n+2m$ edges.

Now let $G''$ be $G'$ but removing all incoming edges from $\bar{s}$ and
all outgoing edges from $\bar{t}$, in order to apply <ref> on $G''$ with $a = \bar{s}$ and $b = \bar{t}$.
Say we get matroids $\cM_1$ and $\cM_2$. Note that
Alice knows $\cM_1$ and Bob knows $\cM_2$ by construction.

Now $s$ and $t$ are connected in $G$ if and only if there is a directed $(\bar{s},\bar{t})$-path in $G''$. This happens if and only if $V$ is not a maximum-cardinality common independent set of $\cM_1$ and $\cM_2$ (i.e. in the case we found an augmenting path for $V$).

Hence if there is a (deterministic) communication protocol for matroid intersection using $c$ bits of communication, there is also one for  using $O(c)$ bits of communication. <ref> then implies the
$\Omega(n\log n)$ communication lower bound for matroid intersection.

[1]
Daniel Anderson and Guy E. Blelloch.
Parallel minimum cuts in O(m
log\({}^{\mbox{2}}\)n) work and low depth.
In SPAA, pages 71–82. ACM, 2021.

[2]
Martin Aigner and Thomas A. Dowling.
Matching theory for combinatorial geometries.
Transactions of the American Mathematical Society,
158(1):231–245, 1971.

[3]
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay,
and Danupon Nanongkai.
Cut query algorithms with star contraction.
In FOCS, pages 507–518. IEEE, 2022.

[4]
Amir Abboud, Robert Krauthgamer, Jason Li, Debmalya Panigrahi, Thatchaphol
Saranurak, and Ohad Trabelsi.
Breaking the cubic barrier for all-pairs max-flow: Gomory-hu tree in
nearly quadratic time.
In FOCS, pages 884–895. IEEE, 2022.

[5]
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
APMF  apsp? gomory-hu tree for unweighted graphs in
almost-quadratic time.
In FOCS, pages 1135–1146. IEEE, 2021.

[6]
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
Subcubic algorithms for gomory-hu tree in unweighted graphs.
In STOC, pages 1725–1737. ACM, 2021.

[7]
Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.
Friendly cut sparsifiers and faster gomory-hu trees.
In SODA, pages 3630–3649. SIAM, 2022.

[8]
Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu.
Circulation control for faster minimum cost flow in unit-capacity
In FOCS, pages 93–104. IEEE, 2020.

[9]
Kyriakos Axiotis, Aleksander Madry, and Adrian Vladu.
Faster sparse minimum cost flow by electrical flow localization.
In FOCS, pages 528–539. IEEE, 2021.

[10]
Arne Andersson.
Improving partial rebuilding by using simple balance criteria.
In WADS, volume 382 of Lecture Notes in Computer
Science, pages 393–402. Springer, 1989.

[11]
Arne Andersson.
Maintaining \(\alpha\)-balanced trees by partial rebuilding.
Int. J. Comput. Math., 38(1-2):37–48, 1991.

[12]
Josh Alman and Virginia Vassilevska Williams.
A refined laser method and faster matrix multiplication.
In SODA, pages 522–539. SIAM, 2021.

[13]
Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, and
Irit Katriel.
Dynamic matchings in convex bipartite graphs.
In MFCS, volume 4708 of Lecture Notes in Computer
Science, pages 406–417. Springer, 2007.

[14]
Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi.
Fast edge splitting and edmonds' arborescence construction for
unweighted graphs.
In SODA, pages 455–464. SIAM, 2008.

[15]
Joakim Blikstad.
Breaking o(nr) for matroid intersection.
In ICALP, volume 198 of LIPIcs, pages 31:1–31:17.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[16]
Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, and
Danupon Nanongkai.
Nearly optimal communication and query complexity of bipartite
In FOCS, pages 1174–1185. IEEE, 2022.

[17]
Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, and Danupon Nanongkai.
Breaking the quadratic barrier for matroid intersection.
In STOC, pages 421–432. ACM, 2021.

[18]
Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, and Aaron Sidford.
Improved lower bounds for submodular function minimization.
In FOCS, pages 245–254. IEEE, 2022.

[19]
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and
Thatchaphol Saranurak.
A deterministic algorithm for balanced cut with applications to
dynamic connectivity, flows, and beyond.
In FOCS, pages 1158–1167. IEEE, 2020.

[20]
Ruoxu Cen, William He, Jason Li, and Debmalya Panigrahi.
Steiner connectivity augmentation and splitting-off in
poly-logarithmic maximum flows.
In SODA, pages 2449–2488. SIAM, 2023.

[21]
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg,
and Sushant Sachdeva.
Maximum flow and minimum-cost flow in almost-linear time.
In FOCS, pages 612–623. IEEE, 2022.

[22]
Ruoxu Cen, Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol
Saranurak, and Kent Quanrud.
Minimum cuts in directed graphs via partial sparsification.
In FOCS, pages 1147–1158. IEEE, 2021.

[23]
Ruoxu Cen, Jason Li, and Debmalya Panigrahi.
Augmenting edge connectivity via isolating cuts.
In SODA, pages 3237–3252. SIAM, 2022.

[24]
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla, and
Sam Chiu-wai Wong.
Faster matroid intersection.
In FOCS, pages 1146–1168. IEEE Computer Society, 2019.

[25]
Michael B. Cohen, Aleksander Madry, Piotr Sankowski, and Adrian Vladu.
Negative-weight shortest paths and unit capacity minimum cost flow in
õ (m\({}^{\mbox{10/7}}\) log W) time (extended abstract).
In SODA, pages 752–771. SIAM, 2017.

[26]
William H. Cunningham.
Improved bounds for matroid partition and intersection algorithms.
SIAM J. Comput., 15(4):948–957, 1986.

[27]
Paul F. Dietz.
Fully persistent arrays (extended array).
In WADS, volume 382 of Lecture Notes in Computer
Science, pages 67–74. Springer, 1989.

[28]
Efim A Dinic.
Algorithm for solution of a problem of maximum flow in networks with
power estimation.
In Soviet Math. Doklady, volume 11, pages 1277–1280, 1970.

[29]
James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre
Making data structures persistent.
In STOC, pages 109–121. ACM, 1986.

[30]
Jack Edmonds.
Submodular functions, matroids, and certain polyhedra.
In Combinatorial structures and their applications, pages
69–87. Gordon and Breach, 1970.

[31]
Jack Edmonds.
Matroids and the greedy algorithm.
Math. Program., 1(1):127–136, 1971.

[32]
Jack Edmonds, GB Dantzig, AF Veinott, and M Jünger.
Matroid partition.
50 Years of Integer Programming 1958–2008, page 199, 1968.

[33]
Jack Edmonds and Delbert Ray Fulkerson.
Transversals and matroid partition.
J. Res. Nat. Bur. Standards Sect. B, 69:147–153, 1965.

[34]
David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig.
Sparsification - a technique for speeding up dynamic graph
J. ACM, 44(5):669–696, 1997.

[35]
Greg N. Frederickson.
Data structures for on-line updating of minimum spanning trees, with
SIAM J. Comput., 14(4):781–798, 1985.

[36]
Greg N. Frederickson and Mandayam A. Srinivas.
Algorithms and data structures for an expanded family of matroid
intersection problems.
SIAM J. Comput., 18(1):112–138, 1989.

[37]
Harold N. Gabow.
A matroid approach to finding edge connectivity and packing
In STOC, pages 112–122. ACM, 1991.

[38]
Harold N. Gabow.
A matroid approach to finding edge connectivity and packing
J. Comput. Syst. Sci., 50(2):259–273, 1995.

[39]
Martin Gardner.
The second scientific american book of mathematical puzzles and
diversions, 1961.

[40]
David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn.
Dynamic graph connectivity with improved worst case update time and
sublinear space.
CoRR, abs/1509.06464, 2015.

[41]
Yu Gao, Yang P. Liu, and Richard Peng.
Fully dynamic electrical flows: Sparse maxflow faster than
In FOCS, pages 516–527. IEEE, 2021.

[42]
Harold N. Gabow and Matthias F. M. Stallmann.
Efficient algorithms for graphic matroid intersection and parity
(extended abstract).
In ICALP, volume 194 of Lecture Notes in Computer
Science, pages 210–220. Springer, 1985.

[43]
Jack E Graver, Brigitte Servatius, and Herman Servatius.
Combinatorial rigidity.
Number 2. American Mathematical Soc., 1993.

[44]
Harold N. Gabow and Robert Endre Tarjan.
Efficient algorithms for simple matroid intersection problems.
In FOCS, pages 196–204. IEEE Computer Society, 1979.

[45]
Harold Gabow and Herbert Westermann.
Forests, frames, and games: algorithms for matroid sums and
In STOC, pages 407–421, 1988.

[46]
Harold N. Gabow and Ying Xu.
Efficient algorithms for independent assignments on graphic and
linear matroids.
In FOCS, pages 106–111. IEEE Computer Society, 1989.

[47]
Nicholas JA Harvey.
Matroid intersection, pointer chasing, and young's seminormal
representation of sn.
In SODA, pages 542–549, 2008.

[48]
Nicholas J. A. Harvey.
Algebraic algorithms for matching and matroid problems.
SIAM J. Comput., 39(2):679–702, 2009.

[49]
John E. Hopcroft and Richard M. Karp.
An n\({}^{\mbox{5/2}}\) algorithm for maximum matchings in bipartite
SIAM J. Comput., 2(4):225–231, 1973.

[50]
András Hajnal, Wolfgang Maass, and György Turán.
On the communication complexity of graph properties.
In STOC, pages 186–191. ACM, 1988.

[51]
Haotian Jiang, Yin Tat Lee, Zhao Song, and Sam Chiu-wai Wong.
An improved cutting plane method for convex optimization,
convex-concave games, and its applications.
In STOC, pages 944–953. ACM, 2020.

[52]
Bruce M. Kapron, Valerie King, and Ben Mountjoy.
Dynamic graph connectivity in polylogarithmic worst case time.
In SODA, pages 1131–1142. SIAM, 2013.

[53]
Tarun Kathuria, Yang P. Liu, and Aaron Sidford.
Unit capacity maxflow in almost
$o(m{4/3})$ time.
In FOCS, pages 119–130. IEEE, 2020.

[54]
Eugene L. Lawler.
Matroid intersection algorithms.
Math. Program., 9(1):31–56, 1975.

[55]
Troy Lee, Tongyang Li, Miklos Santha, and Shengyu Zhang.
On the cut dimension of a graph.
In CCC, volume 200 of LIPIcs, pages 15:1–15:35.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[56]
Andrés López-Martínez, Sagnik Mukhopadhyay, and Danupon
Work-optimal parallel minimum cuts for non-sparse graphs.
In SPAA, pages 351–361. ACM, 2021.

[57]
Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and
Sorrachai Yingchareonthawornchai.
Vertex connectivity in poly-logarithmic max-flows.
In STOC, pages 317–329. ACM, 2021.

[58]
Jason Li and Debmalya Panigrahi.
Deterministic min-cut in poly-logarithmic max-flows.
In FOCS, pages 85–92. IEEE, 2020.

[59]
Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak.
A nearly optimal all-pairs min-cuts algorithm in simple graphs.
In FOCS, pages 1124–1134. IEEE, 2021.

[60]
Yin Tat Lee and Aaron Sidford.
Path finding methods for linear programming: Solving linear programs
in õ(sqrt(rank)) iterations and faster algorithms for maximum flow.
In FOCS, pages 424–433, 2014.

[61]
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong.
A faster cutting plane method and its implications for combinatorial
and convex optimization.
In FOCS, pages 1049–1065. IEEE Computer Society, 2015.

[62]
Troy Lee, Miklos Santha, and Shengyu Zhang.
Quantum algorithms for graph problems with cut queries.
In SODA, pages 939–958. SIAM, 2021.

[63]
Aleksander Madry.
Navigating central path with electrical flows: From flows to
matchings, and back.
In FOCS, pages 253–262. IEEE Computer Society, 2013.

[64]
Aleksander Madry.
Computing maximum flow with augmenting electrical flows.
In FOCS, pages 593–602. IEEE, 2016.

[65]
John H Mason.
On a class of matroids arising from paths in graphs.
Proceedings of the London Mathematical Society, 3(1):55–74,

[66]
Sagnik Mukhopadhyay and Danupon Nanongkai.
Weighted min-cut: sequential, cut-query, and streaming algorithms.
In STOC, pages 496–509. ACM, 2020.

[67]
Huy L. Nguyen.
A note on cunningham's algorithm for matroid intersection.
CoRR, abs/1904.04129, 2019.

[68]
Jürg Nievergelt and Edward M. Reingold.
Binary search trees of bounded balance.
In STOC, pages 137–142. ACM, 1972.

[69]
Danupon Nanongkai and Thatchaphol Saranurak.
Dynamic spanning forest with worst-case update time: adaptive, las
vegas, and o(n\({}^{\mbox{1/2 - {\(\epsilon\)}}}\))-time.
In STOC, pages 1122–1129. ACM, 2017.

[70]
Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen.
Dynamic minimum spanning forest with subpolynomial worst-case update
In FOCS, pages 950–961. IEEE Computer Society, 2017.

[71]
Hazel Perfect.
Applications of menger's graph theorem.
Journal of Mathematical Analysis and Applications,
22(1):96–111, 1968.

[72]
Christopher Price.
Combinatorial algorithms for submodular function minimization and
related problems.
Master's thesis, University of Waterloo, 2015.

[73]
Aviad Rubinstein, Tselil Schramm, and S. Matthew Weinberg.
Computing exact minimum cuts without knowing the graph.
In ITCS, volume 94 of LIPIcs, pages 39:1–39:16.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.

[74]
James Roskind and Robert E. Tarjan.
A note on finding minimum-cost edge-disjoint spanning trees.
Math. Oper. Res., 10(4):701–708, 1985.

[75]
Alexander Schrijver.
Combinatorial Optimization: Polyhedra and Efficiency.
Springer, 2003.

[76]
Claude E Shannon.
Game playing machines.
Journal of the Franklin Institute, 260(6):447–453, 1955.

[77]
Robert Endre Tarjan.
Edge-disjoint spanning trees and depth-first search.
Acta Informatica, 6:171–185, 1976.

[78]
Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard
Peng, and Aaron Sidford.
Faster maxflow via improved dynamic spectral vertex sparsifiers.
In STOC, pages 543–556. ACM, 2022.

[79]
Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron
Sidford, Zhao Song, and Di Wang.
Minimum cost flows, MDPs, and $\ell_1$-regression in nearly linear
time for dense instances.
In STOC, pages 859–869. ACM, 2021.

[80]
Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol
Saranurak, Aaron Sidford, Zhao Song, and Di Wang.
Bipartite matching in nearly-linear time on moderately dense graphs.
In FOCS, pages 919–930. IEEE, 2020.

[81]
Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak.
Dynamic matrix inverse: Improved algorithms and matching conditional
lower bounds.
In FOCS, pages 456–480. IEEE Computer Society, 2019.

[82]
Dominic JA Welsh.
Matroid theory.
Academic Press, London, New York, 1976.

[83]
Walter Whiteley.
The union of matroids and the rigidity of frameworks.
SIAM J. Discret. Math., 1(2):237–255, 1988.

[84]
Christian Wulff-Nilsen.
Fully-dynamic minimum spanning forest with improved worst-case update
In STOC, pages 1130–1143. ACM, 2017.

[85]
Ying Xu and Harold N. Gabow.
Fast algorithms for transversal matroid intersection problems.
In ISAAC, volume 834 of Lecture Notes in Computer
Science, pages 625–633. Springer, 1994.

§ K-FOLD MATROID UNION

In this section, we study the special case of matroid union where we take the $k$-fold union of the same matroid.
That is, a basis of the $k$-fold union of $\cM = (U, \cI)$ is the largest subset $S \subseteq U$ which can be partitioned into $k$ disjoint independent sets $S_1, \ldots, S_k$ of $\cI$.
Many of the prominent applications of matroid union fall into this special case, particularly the $k$-disjoint spanning tree problem.
As a result, here we show an optimized version of the algorithm presented in <ref> with better and explicit dependence on $k$ that works in this regime.