Optimal Parallel Basis Finding in Graphic and Related Matroids

For the setting of graphic matroids, we provide a complete resolution of the complexity of finding a basis when given access to an independence oracle. We first give a deterministic algorithm with $O(\log m)$ rounds and $\mathrm{poly}(m)$ queries per round:

This result resolves an open question posed by [24]: it shows that the adaptive round complexity can be made logarithmic without blowing up the per-round query complexity to super-polynomial.

In fact, since the above theorem can be used to compute the rank of a graphic matroid in $O(\log (m))$ rounds, we can take advantage of [8]’s black-box recipe for finding minimum and maximum weight bases²²2Note that in this setting, each element of the matroid is also given an associated weight. The weight of a basis is the sum of the weights of the constituent elements.:

We complement our algorithmic results with a matching lower bound, ruling out even a randomized algorithm with asymptotically smaller number of rounds when queries per round are restricted to be polynomial.

Together, these results give a complete picture of the parallel complexity landscape for bases in graphic matroids, fully settling the question raised by [24] in this setting.

Beyond the graphic case, we next show that the same cycle-structural framework extends to broader classes: namely binary (${𝔽}_2$-representable) matroids that satisfy a smooth circuit counting bound.

Indeed, with these definitions and by leveraging the toolkit from the graphic matroid setting, we have the following more general algorithmic statement:

In fact, this automatically implies such a bound for the class of cographic matroids. For a graph $G$, its cographic matroid is the matroid whose circuits are precisely the cuts of $G$. Cographic matroids satisfy the smooth circuit counting bound as shown by Karger’s classic cut-counting bound [23], thus yielding the corollary below:

On the other hand, by considering the cographic matroids defined by the family of instances used in lower bound for graphic matroids (Theorem 3), we can also show that these $\mathrm{\Omega }(\log (m))$ rounds are necessary for cographic matroids, thereby also settling the round complexity of basis finding in cographic matroids.

Beyond this, we can even consider the well-studied class of regular matroids (matroids that are representable over every field). For such matroids, the binary condition is true by definition and a weakened form of the smooth circuit counting bound is known to be true. Indeed, the work of Gurjar and Vishnoi [22] showed that in regular matroids, the number of circuits of size $\le \alpha \mathrm{\ell }$ (for $\mathrm{\ell }$ being the minimum circuit size) is at most $m^{O({\alpha }^2)}$. In fact, they even showed that this same bound holds for so-called “max-flow min-cut” matroids, a class that generalizes beyond regular matroids. Intuitively, these are matroids where certain circuit structures in the matroid (analogous to the max flow) are equal to an appropriately defined structure relating to complements of circuits in the dual matroid (analogous to the minimum cut). Such matroids have seen extensive study in their own right, and we refer the reader to [32, 33, 21] for further discussion.

Nevertheless, this raises the tantalizing possibility of whether the counting bound of [21] can be strengthened to match the asymptotics of Definition 5:

As stated above, a proof of Conjecture 8 would immediately imply an $O(\log (m))$-round, $\mathrm{poly}(m)$-query algorithm for all max-flow min-cut matroids. Likewise a proof of Conjecture 8 only for the smaller class of regular matroids would also imply an algorithm of the same complexity for regular matroids. With the statement of our results provided, we now proceed to a discussion of the techniques we use to prove them.

Consider the set of edges given by $C\oplus C^{\prime }$, and let us consider the degree of any vertex $v$. We claim that $v$ will always have degree $0,2$ or $4$ in $C\oplus C^{\prime }$, and thus there must be a cycle in the graph $C\oplus C^{\prime }$ (as it is a non-empty graph with all degrees being even).

To see why, if $v$ has degree $0$ in both $C,C^{\prime }$, then $v$ also has degree $0$ in $C\oplus C^{\prime }$. If $v$ has degree $2$ in $C$, but degree $0$ in $C^{\prime }$ (or vice versa), then $v$ will have degree $2$ in $C\oplus C^{\prime }$, as no edges incident to $v$ are removed. Finally, if $v$ has degree $2$ in both $C$ and $C^{\prime }$, then we must look at how many edges are in common. If $v$ shares $0$ edges between $C,C^{\prime }$ then its degree in the symmetric difference is $4$, if $v$ shares $1$ edge between $C,C^{\prime }$, its degree is $2$, and if it shares both edges between $C,C^{\prime }$, then its degree is $0$ in the symmetric difference. This concludes the proof. $\mathrm{⊲}$

Next, we establish the following lemma, which lower bounds the overlap size between any cycles:

Note that if $k^{\prime }$ is sufficiently large relative to $\mathrm{\ell }$, the above lemma is trivial. For instance, if $k^{\prime }\ge 1.5\mathrm{\ell }$, then $|C^{\prime }\setminus C|\ge k^{\prime }-1.01\mathrm{\ell }\ge k^{\prime }-(3/4)k^{\prime }=\frac{k^{\prime }}{4}$ (using $1.01\mathrm{\ell }\le (3/4)k^{\prime }$ for $k^{\prime }\ge 1.5\mathrm{\ell }$). The interesting case is when $k^{\prime }\le 1.5\mathrm{\ell }$. Here we use Claim 15: since $C\oplus C^{\prime }$ must contain a cycle and $\mathrm{\ell }$ is the shortest cycle length in $G$, we have $|C\oplus C^{\prime }|\ge \mathrm{\ell }$. We can rewrite

Plugging in $|C\oplus C^{\prime }|\ge \mathrm{\ell }$ and using $|C|\le 1.01\mathrm{\ell }$ and $|C^{\prime }|\ge \mathrm{\ell }$, we obtain

which simplifies to

Thus $|C^{\prime }\setminus C|\ge 0.495\mathrm{\ell }$, which in this case is at least $k^{\prime }/4$. $◀$

With these lemmas, we are now ready to start presenting our algorithms. We begin by studying algorithms for recovering unique cycles in graphs using only an independence oracle.

The independence query to $E^{\prime }$ will be $1$ if and only if there are no cycles. $\mathrm{⊲}$

To prove this, we use an auxiliary claim: namely that if a graph $G$ has at least $2$ distinct cycles, then there is no single edge whose removal kills both cycles. To see why, let us denote two cycles by $C_1,C_2$. If an edge $e$ is in both $C_1$ and $C_2$, then by Claim 15, $C_1\oplus C_2$ contains a cycle, and $e\notin C_1\oplus C_2$. Thus, there must be some cycle in the graph which does not include the edge $e$, so $e$’s removal does not disconnect the graph. Otherwise, if $e$ is not in both of $C_1,C_2$, one of $C_1,C_2$ will also remain intact after $e$’s removal. This yields the claim. $\mathrm{⊲}$

Let the cycle be denoted by $C$. Observe that removing any edge $e\in C$ will disconnect the cycle, and hence the independence queries will now return $1$. Likewise, deleting any edge $e\notin C$ will not disconnect the cycle, and the cycle will still be present, so the independence queries will return $0$. $\mathrm{⊲}$

Finally, we also observe that the above algorithm can be implemented in $1$ round of adaptivity:

Notice that the algorithm queries $\mathrm{Ind}(E^{\prime })$, and $\mathrm{Ind}(E^{\prime }\setminus \{e\}):\forall e\in E^{\prime }$. All these queries are made without reference to the results from previous queries. $\mathrm{⊲}$

Thus, we get the following lemma to summarize Algorithm 1:

This follows from Claim 17, Claim 18, Claim 19, and Claim 20. $◀$

Thus, we have a simple algorithm for identifying when there is a single cycle in a graph. In the coming sections, we will show how to use this procedure to identify and remove all of the short cycles in a given graph.

First, we calculate the probability that $C$ survives the sampling procedure. This is straightforward, as $C$ has $\le 1.01\mathrm{\ell }$ edges. So, after sampling at rate $p$, the probability all $\le 1.01\mathrm{\ell }$ edges survive is:

Thus, it remains only to bound the probability that some other cycle $C^{\prime }$ also survives the sampling at rate $p$, conditioned on $C$ surviving the sampling.

Indeed, to bound this, let us suppose that $C^{\prime }$ is of length $k^{\prime }$. By Lemma 16, we know that $|C^{\prime }\setminus C|\ge \frac{k^{\prime }}{4}$. Thus,

as there will be at least $k^{\prime }/4$ edges in $C^{\prime }$ which are not in $C$ (and thus these edges surviving the sampling process is independent of $C$ surviving).

Next, it remains to take a union bound over all possible cycles $C^{\prime }$. For this, let $\alpha$ be the power of $2$ such that $k^{\prime }\in [\alpha \mathrm{\ell },2\alpha \mathrm{\ell }]$, and then we use Claim 14. Specifically, for cycles $C^{\prime }$ of length $[\alpha \mathrm{\ell },2\alpha \mathrm{\ell }]$, we know that there are at most ${(2m)}^{2\alpha }$ such cycles. So, for a fixed $\alpha$, this means we get the following bound:

To conclude, we can then take a union bound over $\alpha \in \{1,2,4,8,\mathrm{\dots }m\}$. Thus, we see that:
$\mathrm{Pr}$ $[\exists C^{\prime }\ne C\text{ that survives sampling}|C\text{ survives sampling}]$ $\le {\displaystyle \sum _{\alpha \in \{1,2,4,8,\mathrm{\dots }m\}}}\mathrm{Pr}[\exists C^{\prime }\ne C\text{ of length }[\alpha \mathrm{\ell },2\alpha \mathrm{\ell }]\text{ that survives sampling}|C\text{ survives sampling}]$ $\le {\displaystyle \sum _{\alpha \in \{1,2,4,8,\mathrm{\dots }m\}}}{\left({\displaystyle \frac{2}{m^{23}}}\right)}^{\alpha }\le {\displaystyle \sum _{\alpha =1}^{\mathrm{\infty }}}{\left({\displaystyle \frac{2}{m^{23}}}\right)}^{\alpha }$ $\le {\displaystyle \frac{4}{m^{23}}}$

where the final inequality follows because the expression is a geometric series with ratio .

Finally, recall that our goal was to show that $C$ is the unique cycle which survives sampling with non-negligible probability. For this, observe that
$$\mathrm{Pr}[C\text{ survives sampling}]=\mathrm{Pr}[C\text{ uniquely survives sampling}]+\mathrm{Pr}[\exists C^{\prime }\ne C:C\wedge C^{\prime }\text{ survive sampling}].$$

Now, this second term we can bound by our above work. I.e.,

Thus, we see that

as we desire. $\mathrm{⊲}$

Using the above claim, we now show that (with high probability) every cycle $C$ of length $(\mathrm{\ell },1.01\mathrm{\ell }]$ is the unique surviving cycle for some $E^{(i)}$ produced by Algorithm 2.

Fix any cycle $C$ in $E$ of length $(\mathrm{\ell },1.01\mathrm{\ell }]$. By Claim 22, we know that over the randomness of the sampling procedure, $C$ will be the unique cycle present in $E^{(i)}$ with probability $\frac{1}{2m^{101}}$. Thus, by repeating this procedure $m^{102}$ times, we know that there is at least one index $i$ for which $C$ is the unique cycle with probability $1-2^{-\mathrm{\Omega }(m)}$.

Now, because there are at most ${(2m)}^5$ cycles of length $(\mathrm{\ell },1.01\mathrm{\ell }]$ in a graph with no cycles of length $\le \mathrm{\ell }$, we can take a union bound over all these cycles. This means that with probability $1-2^{-\mathrm{\Omega }(m)}$, for every cycle $C$ in $E$ of length $(\mathrm{\ell },1.01\mathrm{\ell }]$, there is an index $i\in [m^{102}]$ such that $C$ is the unique cycle in $E^{(i)}$. $◀$

First, recall that by Lemma 21, the algorithm DetectSingleCycle does not return $⟂$ if and only if there is a single cycle in the input graph. By this same lemma, when the output is not $⟂$, the algorithm recovers exactly the constituent edges of the cycle. Hence the output of Algorithm 3 is necessarily a set of cycles (as the cycles in the subsampled graphs will also be cycles in the original graph). It remains only to show that every cycle of length $(\mathrm{\ell },1.01\mathrm{\ell }]$ is included in the output. This follows exactly from Lemma 23. Indeed, every cycle of length $(\mathrm{\ell },1.01\mathrm{\ell }]$ will be the unique cycle surviving the sampling procedure with probability $1-2^{-\mathrm{\Omega }(m)}$, and thus will be included in the output as well. This yields the lemma at hand. $◀$

Likewise, we can observe that Algorithm 3 is implementable in parallel without any adaptivity:

By Lemma 21, each invocation of DetectSingleCycle requires $O(m)$ queries to the independence oracle. Each of the sub-sampled graphs is checked in parallel, and thus the total number of queries is $O(m\cdot m^{102})=\mathrm{poly}(m)$, without any adaptivity. $\mathrm{⊲}$

The first item is essentially trivial. Every cycle in $\mathrm{Cycles}$ has some constituent edge deleted.

The second item is less immediate. To see why the connectivity of $E$ and $E^{\prime }$ is the same, let us consider adding the edges in $E\setminus E^{\prime }$ back in to $E^{\prime }$, in increasing order (i.e., starting with the edge which has the smallest label). Let us denote these edges by $e_1^{\ast },\mathrm{\dots }{e}_g^{\ast }$. We claim that the connectivity of $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }{e}_i^{\ast }\}$ is the same as the connectivity of $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }{e}_{i+1}^{\ast }\}$. For the base case, we show that the connected components of $E^{\prime }$ are the same as the connected components of $E^{\prime }\cup \{e_1^{\ast }\}$. This is because $e_1^{\ast }$ was the smallest labeled edge which was removed. Because it was removed though, this means that there is some cycle $C_1$ for which $e_1^{\ast }$ has the largest label, and hence all other edges in $C_1\setminus \{e_1^{\ast }\}$ are still present in $E^{\prime }$. But, adding $e_1^{\ast }$ then does not alter the connected components, as the vertices connected by $e_1^{\ast }$ are already connected by the edges in $C_1\setminus \{e_1^{\ast }\}$.

Now, we show the general case. I.e., that the connectivity of $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }{e}_i^{\ast }\}$ is the same as the connectivity of $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }{e}_{i+1}^{\ast }\}$. For this, observe that because the $e_j^{\ast }$’s are ordered in terms of their labels, $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }{e}_i^{\ast }\}$ contains every edge whose label is smaller than $e_{i+1}^{\ast }$. In particular, because $e_{i+1}^{\ast }$ was removed, this means that $e_{i+1}^{\ast }$ was the largest labeled edge in some cycle $C_{i+1}$. This means that every edge in $C_{i+1}\setminus \{e_{i+1}^{\ast }\}$ is still in $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }{e}_i^{\ast }\}$. But, adding $e_{i+1}^{\ast }$ then does not alter the connected components, as the vertices connected by $e_{i+1}^{\ast }$ are already connected by the edges in $C_{i+1}\setminus \{e_{i+1}^{\ast }\}$.

To conclude, we simply observe that by induction, this means that the connected components of $E^{\prime }$ are the same as the connected components of $E^{\prime }\cup \{e_1^{\ast },\mathrm{\dots }\}=E$. $◀$

Observe that the set of cycles in line 10 is indeed a set of cycles as per Lemma 21. In particular, every cycle of length $\le 100$ will be recovered, as the algorithm queries all subsets of $\le 100$ edges, and so there will be some query for each cycle. The cycle deletion procedure is exactly that of Lemma 26, and thus all cycles of length $\le 100$ are removed, without altering the connected components of $E$. $\mathrm{⊲}$

This set of cycles recovered includes all cycles of length $\le 1.01\mathrm{\ell }$ with probability $1-2^{-\mathrm{\Omega }(m)}$ by Lemma 24. These cycles are then deleted without altering the connected components as per Lemma 26. $\mathrm{⊲}$

Next, we also bound the number of iterations of the while loop:

First, recall that any connected component on $k$ vertices has $\le k^2$ edges. Thus, for a set $E$ of $m$ edges, any spanning forest must have $\ge \sqrt{m}$ edges. Thus, as long as the set of connected components defined by $E$ has not changed under deleting edges, the number of remaining edges must be $\mathrm{\Omega }(\sqrt{m})$.

Next, observe that the set of edges $E$ in the input to line 14 has no cycles of length $\le 100$ as per Claim 27 (but still has $\mathrm{\Omega }(\sqrt{m})$ edges). Now, by Claim 28, with probability $1-2^{-\mathrm{\Omega }(\sqrt{m})}$, all cycles of length $\le 100\cdot 1.01$ are removed.

In general, observe that for an integer $k\ge 100$, it must be the case that

This is because

and for $k\ge 100$, we can write $k=\alpha \cdot 100+kmod100$ for $\alpha \ge 1$. This means

while

Thus,

Thus, if we let $\mathrm{\ell }$ denote the minimum cycle length for an iteration of the while loop in line 14, after this iteration, the new minimum cycle length will be $\ge 1.005\mathrm{\ell }$. After $O(\log (m))$ iterations, the minimum cycle length will be $\ge m+1$, and thus there will be no cycles remaining. In particular, this also means that the number of edges remaining (denoted by $|E|$) is less than the minimum cycle length, and so the stopping condition of the while loop is met.

Note that the probability bound holds because in each iteration there are $\mathrm{\Omega }(\sqrt{m})$ edges remaining (where $m$ denotes the initial number of edges), and each iteration increases the cycle length by a factor of $\ge 1.005$ with probability $1-2^{-\mathrm{\Omega }(\sqrt{m})}$. Thus, we can afford to take a union bound over each iteration failing. This yields the claim. $\mathrm{⊲}$

We conclude with our primary theorem:

To see the bound on the number of queries, and rounds of adaptivity, recall that each invocation of $\mathrm{DetectSingleCycle}$ requires $O(m)$ queries to the oracle by Lemma 21. In each round, there are $\mathrm{poly}(m)$ invocations made to Lemma 21 (in parallel), and thus the total number of queries per round is $\mathrm{poly}(m)$. Likewise, by Claim 29, the number of rounds required is $O(\log (m))$, and returns a spanning forest of $E$ with probability $1-2^{-\mathrm{\Omega }(\sqrt{m})}$. This yields the theorem. $◀$