Deterministic $(2/3-\epsilon )$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries

The matroid intersection problem is one of the most fundamental problems in combinatorial optimization. In this problem, we are given two matroids ${ℳ}_1=(V,{ℐ}_1)$ and ${ℳ}_2=(V,{ℐ}_2)$ defined on the same ground set $V$ of $n$ elements, and the objective is to find a common independent set $S\in {ℐ}_1\cap {ℐ}_2$ of largest possible cardinality, denoted by $r$. This problem generalizes many important combinatorial optimization problems such as bipartite matching, packing spanning trees, and arborescences in directed graphs. Furthermore, it has also several applications outside of traditional combinatorial optimization such as electrical engineering [51, 55].

To design an algorithm for arbitrary matroids, it is common to consider an oracle model: an algorithm accesses a matroid through an oracle. The most standard and well-studied oracle is an independence oracle, which takes as input a subset $S\subseteq V$ and outputs whether $S$ is independent or not. Many studies consider the following research question: how few queries can we solve the matroid intersection problem with?

Starting the work of Edmonds [22, 23], many algorithms with polynomial query complexity for the matroid intersection problem have been studied [4, 48, 21, 57, 49, 20, 36, 52, 18, 15, 11, 60, 13, 9, 53, 14]. Edmonds [22] developed the first polynomial-query algorithm by reduction to the matroid partitioning problem. This algorithm requires $O(n^4)$ independence oracle queries. More direct algorithms were given by Aigner–Dowling [4] and Lawler [48]. The algorithm of Lawler requires $O(n{r}^2)$ independence oracle queries. In 1986, Cunningham [21] presented an $O(n{r}^{3/2})$-independence-query algorithm by using a blocking flow approach, which is akin to the bipartite matching algorithm of Hopcroft–Karp [35]. Chekuri–Quanrud [20] pointed out that, for any $\epsilon >0$, an $O(nr/\epsilon )$-independence-query $(1-\epsilon )$-approximation algorithm can be obtained by terminating Cunningham’s algorithm early. This idea comes from the well-known fact that, for the bipartite matching problem, a linear-time $(1-\epsilon )$-approximation algorithm can be obtained by terminating Hopcroft–Karp’s algorithm early. Recently, Nguy$\widetilde{\widehat{\text{e}}}$n [52] and Chakrabarty–Lee–Sidford–Singla–Wong [18] independently presented a new binary search technique that can efficiently find edges in the exchange graph and developed a combinatorial $\tilde{O}(nr)$-independence-query exact algorithm.¹¹1The $\tilde{O}$ notation omits factors polynomial in $\log n$. Chakrabarty et al. also presented a new augmenting sets technique and developed an $\tilde{O}(n^{1.5}/{\epsilon }^{1.5})$-independence-query $(1-\epsilon )$-approximation algorithm. The techniques developed by Nguy$\widetilde{\widehat{\text{e}}}$n and Chakrabarty et al. have been used in recent several studies on fast algorithms for other matroid problems [12, 58, 61, 54, 43, 16]. Blikstad–van den Brand-Mukhopadhyay–Nanongkai [15] first broke the $\tilde{O}(n^2)$-independence-query bound for exact matroid intersection algorithms. Blikstad [11] improved the independence query complexity of a $(1-\epsilon )$-approximation algorithm to $\tilde{O}(n\sqrt{r}/\epsilon )$. Blikstad’s improvement on the $(1-\epsilon )$-approximation algorithm resulted in a randomized $\tilde{O}(n{r}^{3/4})$-independence-query exact algorithm and a deterministic $\tilde{O}(n{r}^{5/6})$-independence-query exact algorithm. Recently, Quanrud [53] presented a randomized ${\tilde{O}}_{\epsilon }(n+r^{3/2})$-independence-query $(1-\epsilon )$-approximation algorithm²²2The ${\tilde{O}}_{\epsilon }$ notation omits factors polynomial in $\epsilon$ and $\log n$.. Remarkably, Blikstad-Tu [14] very recently presented a randomized ${\tilde{O}}_{\epsilon }(n)$-independence-query $(1-\epsilon )$-approximation algorithm.³³3 The results in this manuscript were obtained independently of the remarkable result by Blikstad–Tu [14].

Both the recent $(1-\epsilon )$-approximation algorithms by Quanrud [53] and Blikstad–Tu [14] are randomized. Therefore, it remains an open question whether a deterministic ${\tilde{O}}_{\epsilon }(n)$ independence-query $(1-\epsilon )$-approximation algorithm can be achieved for almost the entire range of $r$.⁴⁴4Blikstad–Tu [14] presented a deterministic $(1-\epsilon )$-approximation algorithm using a strictly linear number of independence oracle queries only when $r=\mathrm{\Theta }(n)$ (and $\epsilon$ is constant). Then, we consider a deterministic matroid intersection algorithm with only a nearly linear number of independence oracle queries. It is well-known that any maximal common independent set is at least half the size of a maximum common independent set (see e.g., [47, Proposition 13.26]). Thus, the natural greedy algorithm – pick an element whenever possible – can be regarded as a deterministic $1/2$-approximation algorithm using a linear number of independence oracle queries. In fact, even beating the trivial $1/2$-approximation ratio for deterministic nearly-linear-independence-query algorithms remains an open problem for almost the entire range of $r$.⁴⁴4Blikstad–Tu [14] presented a deterministic $(1-\epsilon )$-approximation algorithm using a strictly linear number of independence oracle queries only when $r=\mathrm{\Theta }(n)$ (and $\epsilon$ is constant).

In this work, we present a deterministic $(2/3-\epsilon )$-approximation algorithm using a nearly linear number of independence oracle queries.

Our algorithm uses only a strictly linear number of independence oracle queries when $r=O(n/\log n)$ (and $\epsilon$ is constant). Prior to our work, Guruganesh–Singla [34] presented a randomized $O(n)$-independence-query algorithm that achieves $(1/2+\delta )$-approximation for some small constant $\delta >0$, which was the best approximation ratio for (possibly randomized) algorithms using only a strictly linear number of independence oracle queries.⁴⁴4Blikstad–Tu [14] presented a deterministic $(1-\epsilon )$-approximation algorithm using a strictly linear number of independence oracle queries only when $r=\mathrm{\Theta }(n)$ (and $\epsilon$ is constant).

We note that the time complexity of our algorithm is dominated by the independence oracle queries. That is, our algorithm in Theorem 1 has time complexity $O\left((\frac{n}{\epsilon }+r\log r)\cdot {𝒯}_{\text{ind}}\right)$, where ${𝒯}_{\text{ind}}$ denotes the maximum running time of a single independence oracle query.

Our idea is very simple: we apply a recent $\tilde{O}(n\sqrt{r}/\epsilon )$-independence-query $(1-\epsilon )$-approximation algorithm of Blikstad [11], but terminate it before completion. We observe that a $(2/3-\epsilon )$-approximate solution can be obtained by terminating Blikstad’s algorithm early. As such, our algorithm does not introduce technical novelty, but we believe that it enhances the understanding of algorithms for the matroid intersection problem.

We also implement our algorithm using a rank oracle, which takes as input a subset $S\subseteq V$ and outputs the size of the maximum cardinality independent subset of $S$. Several recent studies have considered fast matroid intersection algorithms in the rank oracle model [49, 18, 60]. We note that the rank oracle is more powerful than the independence oracle, since a single query to the rank oracle can determine whether a given set is independent or not.

Chakrabarty–Lee–Sidford–Singla–Wong [18] presented an $\tilde{O}(n\sqrt{r})$-rank-query exact algorithm and an $O(\frac{n}{\epsilon }\log n)$-rank-query $(1-\epsilon )$-approximation algorithm. Their $(1-\epsilon )$-approximation algorithm requires nearly linear rank oracle queries. Our second result is to obtain a $(2/3-\epsilon )$-approximation algorithm using a strictly linear number of rank oracle queries.

We note that the time complexity of our algorithm is dominated by the rank oracle queries. That is, our algorithm in Theorem 2 has time complexity $O\left(\frac{n}{\epsilon }\cdot {𝒯}_{\text{rank}}\right)$, where ${𝒯}_{\text{rank}}$ denotes the maximum running time of a single rank oracle query.

Surprisingly, our algorithm can also be implemented in the semi-streaming model of computation. The streaming model for graph problems was initiated by Feigenbaum–Kannan–McGregor–Suri–Zhang [27], which is called the semi-streaming model. In this model, an algorithm computes over a graph stream using a limited space of $\tilde{O}(n)$ bits, where $n$ is the number of vertices. The maximum matching problem is one of the most studied problems in the graph streaming setting [27, 50, 25, 1, 33, 24, 45, 2, 42, 26, 41, 3, 44, 59, 31, 8, 6, 7, 30, 40, 10, 46, 29, 5]. The first of these studies was a $(2/3-\epsilon )$-approximation algorithm for the bipartite maximum matching problem by Feigenbaum et al. [27], which uses $\tilde{O}(n)$ bits of space and $O(\log (1/\epsilon )/\epsilon )$ passes. In particular, whether a $(1-\epsilon )$ approximation can be achieved in $\text{poly}(1/\epsilon )$ passes in the semi-streaming model for general graphs was a significant open problem until it was solved by Fischer–Mitrović–Uitto [30].

Since the matroid intersection problem is a well-known generalization of the bipartite matching problem, there are also several studies on the matroid intersection problem (and its generalizations) in the streaming setting in the literature [19, 28, 32, 37, 38, 39, 17]. For the matroid intersection problem, in the semi-streaming model, we consider algorithms such that the memory usage is $O((r_1+r_2)\text{polylog}(r_1+r_2))$, where $r_1$ and $r_2$ denote the ranks of matroids ${ℳ}_1$ and ${ℳ}_2$, respectively. We note that this memory requirement is natural when we formulate the bipartite matching problem as the matroid intersection problem. In this work, we focus on constant-passes ($\text{poly}(1/\epsilon )$-passes) semi-streaming algorithms for the matroid intersection problem, particularly given the significance of constant-passes semi-streaming algorithms for the matching problem.⁵⁵5Based on the results from Assadi [5] and Quanrud [53], we believe that it is able to develop a semi-streaming $(1-\epsilon )$-approximation algorithm with similar space usage. However, such an algorithm would require $O(\log (n)\cdot \text{poly}(1/\epsilon ))$ passes. In the context of research on streaming matching algorithms, the distinctions between $O(\text{poly}(1/\epsilon ))$ passes and $O(\log (n)\cdot \text{poly}(1/\epsilon ))$ are well recognized and crucial; see [5, Table 1 in the arXiv version]. We also believe that the result by Blikstad–Tu [14] is unlikely to immediately lead to constant-passes semi-streaming algorithm for the matroid intersection problem. This is because, while Blikstad–Tu used some idea from the constant-passes semi-streaming algorithm of Assadi-Liu-Tarjan [8] for the bipartite matching problem, Blikstad–Tu relies on the technique from Quanrud [53]. Quanrud’s algorithm used some idea from the $O(\log (n)\cdot \text{poly}(1/\epsilon ))$-passes semi-streaming algorithm by Assadi [5]. Recently, Huang–Sellier [37] presented a $(2/3-\epsilon )$-approximation semi-streaming algorithm for the matroid intersection problem in the random-order streaming model.⁶⁶6We note that their algorithm requires too many queries to compute the density-based decomposition. Thus, their algorithm does not imply a nearly-linear-independence-query $(2/3-\epsilon )$-approximation algorithm.

Our third result is to obtain a $(2/3-\epsilon )$-approximation semi-streaming algorithm with $O(\frac{1}{\epsilon })$ passes in the adversary-order streaming model.

Our algorithm in Theorem 3 is a generalization of the bipartite matching semi-streaming algorithm of Feigenbaum et al. [27].

In this section, we recall the definition and properties of augmenting sets, which were introduced as a generalization of augmenting paths by Chakrabarty–Lee–Sidford–Singla–Wong [18]. The augmenting sets technique plays a crucial role in the $(1-\epsilon )$-approximation algorithms of Chakrabarty et al. [18] and Blikstad [11].

In our matroid intersection algorithm, we only need to find an augmenting set in the exchange graph whose shortest $(s,t)$-path length is $4$. Thus, we introduce the definition and properties of augmenting sets when restricted to the case where the length of a shortest augmenting path is $4$.

Here, we recall the definition and property of maximal augmenting sets, which correspond to a maximal collection of shortest augmenting paths such that augmentation along them must increase the $(s,t)$-distance. In the $(1-\epsilon )$-approximation algorithms of Chakrabarty et al. and Blikstad, they repeatedly find a maximal augmenting set and augment along it.

Here, we recall the definition of partial augmenting sets, which are the relaxed form of augmenting sets. In the algorithms of Chakrabarty et al. and Blikstad for finding a maximal augmenting set, they keep track of the partial augmenting set, which is iteratively made close to a maximal augmenting set through some refine procedures.

Chakrabarty et al. presented an efficient algorithm to convert any partial augmenting set $\mathrm{\Phi }$ into an augmenting set $\mathrm{\Pi }$.

Chakrabarty et al. [18] presented an algorithm to find a maximal augmenting set in the exchange graph $G(S)$, where shortest augmenting paths have length $2(\mathrm{\ell }+1)$, using $O(n^{1.5}\sqrt{\mathrm{\ell }\log r})$ independence oracle queries; see [18, Proof of Theorem 48 and Proof of Theorem 21]. Blikstad [11] improved the query complexity and presented an algorithm to find a maximal augmenting set using $O(n\sqrt{r\log r})$ independence oracle queries; see [11, Lemma 35 and Proof of Theorem 1].

In Blikstad’s algorithm for finding a maximal augmenting set, we keep track of a partial augmenting set and iteratively update it to closer to a maximal augmenting set. To obtain a fast algorithm, Blikstad combines two algorithms Refine [11, Algorithm 4] and RefinePath [11, Algorithm 5]; see [11, Algorithm 6 and Lemma 35]. Let $p\in [1,r]$ be the parameter that controls the trade-off of the two algorithms. He first applies Refine to find a partial augmenting set that is close enough to a maximal augmenting set, which uses $O(nr/p)$ independence oracle queries. Then, he applies RefinePath until the partial augmenting set becomes a maximal augmenting set, which uses $O(np\log r)$ independence oracle queries.

In our algorithm, we apply only the first part Refine of Blikstad’s algorithm, as formally stated as follows.

To obtain Lemma 15, we apply Refine [11, Algorithm 4] (see also Algorithm 5) until $|B_1|-|B_2|\le p$, but at least once. The procedure Refine makes the partial augmenting set $\mathrm{\Phi }=(B_1,A_1,B_2)$ close to a maximal augmenting set. To become $|B_1|-|B_2|\le p$, we need to apply Refine $O(|S|/p+1)$ times; see [11, Proof of Lemma 35]. Since each call of Refine uses $O(n)$ independence oracle queries (see [11, Lemma 29]), the total number of independence oracle queries is $O(nr/p)$.

In this section, by providing a nearly-linear-independence-query $(2/3-\epsilon )$-approximation algorithm for the matroid intersection problem, we prove Theorem 1, which we restate here.

We use the following lemma to prove Theorem 1.

In this section, by providing a linear-rank-query $(2/3-\epsilon )$-approximation algorithm for the matroid intersection problem, we prove Theorem 2. We show that Algorithm 2 can be implemented as a $(2/3-\epsilon )$-approximation algorithm with linear rank oracle queries. We restate Theorem 2 here.

Chakrabarty–Lee–Sidford–Singla–Wong [18] showed that a $(1-\epsilon )$-approximate solution can be obtained with $O(\frac{n}{\epsilon }\log n)$ rank oracle queries by using the binary search technique; see [18, Theorem 17]. In their $(1-\epsilon )$-approximation algorithm, they find some edges using the binary search technique. For each edge, this requires $O(\log n)$ rank oracle queries. On the other hand, we show that a $(2/3-\epsilon )$-approximate solution can be obtained with only $O(n/\epsilon )$ rank oracle queries. In our $(2/3-\epsilon )$-approximation algorithm, we find an almost maximal augmenting set without needing to identify any specific edges. Hence, the rank oracle query complexity of our algorithm is linear without any logarithmic factor.

We use the following lemma to prove Theorem 2.

In this section, by providing a $(2/3-\epsilon )$-approximation algorithm for the matroid intersection problem in the semi-streaming model, we prove Theorem 3. We show that Algorithm 2 can also be implemented in the semi-streaming model as a $(2/3-\epsilon )$-approximation algorithm using a constant number of passes. We restate Theorem 3 here.

Before we present how Algorithm 2 can be implemented in the semi-streaming model, we describe the outline of Blikstad’s [11] algorithm of Lemma 15. This is because some of his results will be used in our argument later. In this paper, we skip the proof of the correctness of the algorithm; see [11, Sections 3.1 and 3.3] for the proof. Recall that, in Lemma 15, we apply Refine only $O(1/\epsilon )$ times. See Algorithm 5 for the pseudocode of Refine.

In Blikstad’s algorithm, we maintain three types of elements in each layer (see [11, Section 3.1]):

• $\mathrm{■}$

  fresh. Denoted by $F_i\subseteq D_i$. These elements are candidates that could be added to the partial augmenting set.

• $\mathrm{■}$

  selected. Denoted by $B_1,A_1,B_2$. These elements form the current partial augmenting set $\mathrm{\Pi }=(B_1,A_1,B_2)$.

• $\mathrm{■}$

  removed. Denoted by $R_i\subseteq D_i$. These elements are deemed useless, and then we can disregard them.

For convenience, we also define imaginary layers $D_0$ and $D_4$ with $A_0=R_0=F_0=D_0=A_2=R_4=F_4=D_4=\mathrm{\varnothing }$.

In Refine (Algorithm 5), we iteratively apply RefineAB (Algorithm 3) and RefineBA (Algorithm 4), and then update the types of elements. Initially, we begin with all elements being fresh. Elements can change their types from fresh $\to$ selected $\to$ removed, but their types cannot be changed in the other direction. Note that an element of type fresh can change to type removed without first going through type selected.

Now, by providing how Algorithm 2 can be implemented in the semi-streaming model, we give a proof of Theorem 3.

We have observed that a $(2/3-\epsilon )$-approximate solution can be obtained by terminating Blikstad’s [11] algorithm early. Then, we obtained a deterministic nearly-linear-independence-query $(2/3-\epsilon )$-approximation algorithm for the matroid intersection problem.

We were also able to use this observation in the streaming model of computation. Then, we obtain a $(2/3-\epsilon )$-approximation constant-pass semi-streaming algorithm for the matroid intersection problem. This result is a generalization of the $(2/3-\epsilon )$-approximation bipartite matching semi-streaming algorithm of Feigenbaum–Kannan–McGregor–Suri–Zhang [27], who initiated the study of matching algorithms in the semi-streaming model. Soon after, McGregor [50] first obtained a $(1-\epsilon )$-approximation constant-pass semi-streaming algorithm for the maximum matching problem. Since then, there have been many studies for $(1-\epsilon )$-approximation constant-pass semi-streaming algorithms for the maximum matching problem in the literature [25, 1, 24, 42, 59, 31, 8, 30, 40]. Then, it is natural to ask whether we can obtain a $(1-\epsilon )$-approximation constant-pass semi-streaming algorithm for the matroid intersection problem.

In the current Blikstad’s algorithm for finding an augmenting set, it is necessary to perfectly find an augmenting set of length $2k$ before finding an augmenting set of length $2k+2$. By finding a maximal common independent set, we can perfectly find an augmenting set of length 2. This means that we can start from a state where shortest augmenting paths have length 4 or greater. In our current algorithm, since we do not perfectly find an augmenting set of length 4, we are unable to find an augmenting set of length 6 or greater. Thus, our current algorithm achieves only a $(2/3-\epsilon )$-approximation rather than a $(1-1/k-\epsilon )$-approximation. However, we believe our study could be an important step to obtain a deterministic nearly-linear-independence-query $(1-\epsilon )$-approximation algorithm.