Cut-Query Algorithms with Few Rounds

We show that the polylogarithmic round complexity of previous work is not necessary for finding a global minimum cut. We begin by presenting two results for unweighted graphs. The first one shows that using even two rounds, we can substantially improve on the $O(n^2)$ query complexity of the naive algorithm. All of our algorithms return a vertex set $S\subseteq V$ and the value of the minimum cut. In the case of unweighted graphs the algorithms can also report the edges of the cut using one additional round of queries and with the same asymptotic query complexity.

We further provide a smooth tradeoff between the number of queries and the number of rounds, namely $\tilde{O}(n^{1+1/r}/\delta {(G)}^{1/r})$ cut queries with in $2r$ rounds, where $\delta (G)\ge 1$ is the minimum degree of $G$.³³3We can assume that the graph is connected since connectivity can be checked using $\tilde{O}(n)$ cut queries in $1$ round (non-adaptive) [4].

We also obtain a similar tradeoff also for weighted graphs.

Finally, we note that our techniques can also be applied to approximating the maximum cut and finding a minimum $(s,t)$-cut with low adaptivity. Furthermore, our result for weighted minimum cuts can also be applied to finding a minimum cut in dynamic streams, providing a smooth tradeoff between the number of passes and the storage complexity of the algorithm. This holds since each cut query in a given round can be computed using $O(\log n)$ storage in a single pass by simply counting the edges in the cut. Therefore, the round complexity of our algorithm translates immediately to the number of passes required by a streaming algorithm. These results are detailed in the full version of the paper.

Our first technical contribution is a procedure for non-adaptive uniform edge sampling using $O({\log }^{3}n/\log \log n)$ queries that returns the weight of the sampled edge. An algorithm for uniform edge sampling using $O({\log }^{3}n)$ cut queries in one round (i.e. non-adaptively) was proposed in [4].⁴⁴4The algorithm requires $O({\log }^{2}n\log (1/\delta ))$ cut queries and succeeds with probability $1-\delta$, setting $\delta =n^{-2}$ yields the bound. However, their algorithm is based on group testing principles using BIS queries⁵⁵5A BIS query is given two disjoint sets $A,B\subseteq V$ and returns true if there exists some edge connecting $A,B$ and false otherwise. and returns only the endpoints of the edge, but not its weight, though it is probably not difficult to adapt their algorithm to return the weight as well. Our algorithm slightly improves on the query complexity of their algorithm, while also returning the edge’s weight in the same round.

The algorithm works by subsampling the vertices in $T$ into sets $T=T_0\supseteq T_1\supseteq \mathrm{\dots }\supseteq T_{\log n}$, and finds a level $i$ such that . It then leverages sparse recovery techniques to recover all the edges in $E(s,T_i)$ and return one of them at random. To perform this algorithm in one round the algorithm recovers $w(E(s,T_i))$ and performs the queries needed for sparse recovery for all levels in parallel. It then applies the sparse recovery algorithm to the last level with non-zero number of edges, i.e. the last level with $w(E(s,T_i))>0$. We note that it is easy to decrease the query complexity of Lemma 2.1 by a factor of $O(\log n)$ by adding a round of queries and performing the sparse recovery only on the relevant level.

Our second procedure performs weight-proportional edge sampling in two rounds.

The algorithm follows the same basic approach as the uniform edge sampling primitive, i.e. creating nestled subsets $T=T_0\supseteq T_1,\supseteq \mathrm{\dots }\supseteq T_{\log (nW)}$ by subsampling. However, instead of recovering only the edges that were sampled into the last level with non-zero weight, the algorithm recovers in each level $i$ all edges $e\in E(s,T_i)$ such that $w(e)\approx w(E(s,T))/2^i$. The recovery procedure is based on a Count-Min data structure [23], which we show can be implemented using few non-adaptive cut queries. The algorithm then uses another round of queries to learn the exact weights of all edges that were recovered in all the levels. It then concludes by sampling an edge from the distribution $\{p_e\}$, where for every edge $e$ recovered in the $i$-th level, it sets $p_e\propto 2^{i}w(e)/w(E(s,T))$; with probability $1-{\sum }_e{p}_e$, the algorithm fails. Since the probability of being sampled into the $i$-th level is $2^{-i}$, these probabilities yield the desired distribution over the recovered edges.

To prove that the algorithm returns an edge with high probability, we show that there is a constant probability that the outlined procedure returns some edge $e\in E(s,T)$, and hence repeating the algorithm $O(\log n)$ times yields with high probability an edge sampled from $E(s,T)$ with the desired distribution. The query complexity of the algorithm is dominated by the Count-Min data structure, which requires $O(\log n\log (nW))$ cut queries in each level. Applying the recovery procedure on $O(\log (nW))$ levels, and repeating the procedure $O(\log n)$ times yields the stated query complexity.

The key idea of our algorithm is to apply an edge contraction technique that produces a graph with substantially fewer edges while preserving each minimum cut with constant probability. We then recover the entire contracted graph using a limited number of cut queries by applying existing graph recovery methods using $\tilde{O}(m)$ additive queries [22, 14]. We show that it is possible to simulate $k$ additive queries using $O(n+k)$ cut queries, which allows us to recover a graph with $m\ge \tilde{O}(n)$ edges using $O(m)$ cut queries.

While there has been frequent use of contraction procedures for finding minimum cuts, existing algorithms focused on reducing the number of vertices in the graph [28, 26, 3], typically to $\tilde{O}(n/\delta (G))$. This does not suffice to guarantee a graph with few edges, for example, applying such a contraction on a graph $G$ with minimum degree $\delta (G)={\log }^{2}n$ and $\mathrm{\Omega }(n)$ vertices of degree $n$, might yield a graph with $\tilde{\mathrm{\Omega }}(n^2)$ edges. In contrast, our goal is to reduce the number of edges in the graph, allowing efficient recovery of the contracted graph using Corollary 2.3. The main technical contribution of this section is a new contraction algorithm, which we call $\tau$-star contraction, that reduces the number of edges to $\tilde{O}({(n/\tau )}^2+n\tau )$.

Our contraction algorithm is a thresholded version of the star-contraction algorithm introduced in [3]. The original version of the star-contraction algorithm of [3] can be roughly described as follows. Sample a subset of center vertices $R\subseteq V$ uniformly at random with probability $p=O(\log n/\delta (G))$. For every $v\in V\setminus R$, choose uniformly a vertex in $r\in N_G(v)\cap R$ and contract the edge $(v,r)$, keeping parallel edges, which yields a contracted multigraph $G^{\prime }$. The main guarantee of the algorithm is that if the minimum cut of $G$ is non-trivial, i.e. not composed of a single vertex, then $\lambda (G)=\lambda (G^{\prime })$ with constant probability, where $\lambda (G)$ denotes the value of a minimum cut in a graph. The following theorem states this formally.

Note that in the cut query model, the algorithm cannot contract an edge because the underlying cut function remains constant. However, it can simulate the contraction of $e=(u,v)$ by merging the vertices $u$ and $v$ into a supervertex in all subsequent queries, which yields a contracted cut function. We now define our $\tau$-star contraction algorithm.

Notice that $\tau$-star contraction depends on uniform edge sampling, since each vertex $u\in H\setminus R$ samples a neighbor in $R$. In our case, we can use the uniform edge sampling procedure described above to sample edges uniformly from $E(u,R)$.

We now sketch the proof that $\tau$-star contraction yields a graph with few edges. To bound the number of edges, partition the vertices remaining after the contraction into two sets, $R$, i.e. the center vertices sampled in the sampling process, and $L=V\setminus H$, i.e. the low degree vertices. This analysis omits vertices in $H\setminus R$ that were not sampled into $R$ or contracted, because every $v\in H\setminus R$ has in expectation $d_G(v)\cdot \log n/\tau \in \mathrm{\Omega }(\log n)$ neighbors in $R$; hence with high probability it will have some neighbor in $R$ and be contracted.

To bound the number of edges observe that $|R|\le \tilde{O}(n/\tau )$ with high probability, and hence the number of edges between vertices in $R$ is $O({|R|}^2)\le \tilde{O}(n^2/{\tau }^2)$. In addition, since the degree of the vertices of $L$ is bounded by $\tau$, the total number of edges incident on $L$, even before the contraction, is $O(n\tau )$. Hence, the total number of edges in $G^{\prime }$ is with high probability $\tilde{O}(n^2/{\tau }^2+n\tau )$. The following lemma, proved in the full version of the paper, formalizes the guarantees of $\tau$-star contraction.

We present in Algorithm 1 a procedure for finding the global minimum cut in two rounds using $\tau$-star contraction. We will use it to prove Theorem 1.3, but first we need the following claim.

This section provides an algorithm for finding a minimum cut in $2r$ rounds, thus proving Theorem 1.4. The algorithm uses a known approach of first applying a contraction algorithm, yielding a graph with $\tilde{O}(n/\delta (G))$ vertices, and then packing $\delta (G)$ edge-disjoint forests in the contracted graph. The main challenge in adapting this algorithm to low round complexity, is ensuring that the forests are edge disjoint when packing them in parallel. This is achieved by leveraging a connection to cut sparsification, which shows that sampling edges with probabilities amplified by a factor of $k$ relative to those needed for sparsifier construction ensures finding $k$ edge disjoint forests within the sampled subset. We note that we also offer another algorithm for finding a minimum cut, that has slightly worse query complexity of $O(r{n}^{1+1/r})$, and is based on constructing a cut sparsifier and the results of [33], see the full version of the paper.

The contraction we use is the $2$-out contraction procedure of [26], which is obtained by sampling uniformly two edges incident to each vertex and contracting all the sampled edges. The following theorem states the guarantees of the $2$-out contraction.

The other building block of the algorithm is maximal $k$-packing of forests.

We now outline the algorithm of Lemma 2.10, for further details see the full version of the paper. The algorithm begins by creating a set of empty trees $T_1,\mathrm{\dots },T_k$. Then, in each of $r-1$ rounds it uniformly samples $\tilde{O}(k{n}^{1+1/r})$ edges from the graph, augments the trees $\{T_i\}$ by adding all sampled edges that do not form a cycle, and contracts all vertices that are connected in all trees. We show that the number of edges decreases by an $n^{1/r}$ factor in each round; hence, after $r-1$ rounds the number of remaining edges is $O(n^{1+1/r})$. Finally, the algorithm recovers all remaining edges by sampling $\tilde{O}(n^{1+1/r})$ edges uniformly, which recovers all edges by a standard coupon collector argument, and augments the trees appropriately.

To guarantee the decrease in the number of edges we leverage an elegant connection to cut sparsifier contraction. The seminal work [13] showed that if we sample (and reweight) every edge with probability proportional to its strong connectivity, then the resulting graph approximates all the cuts of the original graph with high probability.

We also need the following lemma concerning the existence of $\kappa$-strong components in a graph.

We can now detail the process of edge reduction of Lemma 2.10. Let $G$ be a graph with $m$ edges and $n$ vertices. Observe that after one round of sampling, the algorithm contracts every $(m/n^{1+1/r})$-strong component of $G$, and thus by Lemma 2.12 the number of edges remaining in the graph is at most $m/n^{1/r}$. Let $C\subseteq V$ be a maximal $\mathrm{\Omega }(m/n^{1+1/r})$-strong component of $G$, and assume the algorithm samples every edge of the graph with probability $p_e\approx k/\kappa$. In expectation the algorithm samples at least $p_e\cdot m/n^{1+1/r}\approx k$ edges crossing each cut $S\subseteq C$, which also holds with high probability by standard concentration and cut counting results. Therefore, for every $u,v\in C$, the minimum cut in the sampled subgraph has at least $k$ edges, hence they are connected in $k$ edge disjoint forests and will be contracted. In conclusion, in every iteration the algorithm contracts all $(m/n^{1+1/r})$-strong components of the graph, and the number of edges in the graph decreases by a factor of $n^{1/r}$.

In this section we give an overview of our algorithm for minimum cut in a weighted graph with low adaptivity. It is an adaptation of the minimum cut algorithm of [31], which reduces the problem to constructing a cut sparsifier and solving a monotone matrix problem which is easily parallelizable. The main difficulty lies within the construction of a cut sparsifier; while previous work in the cut-query model already provided cut sparsifiers [33, 32], its core step, weight-proportional edge sampling, uses $O(\log n)$ rounds. Our main technical contribution here is our two-round weight-proportional edge sampling primitive (Lemma 2.2), which enables the construction of a $(1\pm ϵ)$-cut-sparsifier in $3r$ rounds and the completion of the entire reduction within $O(r)$ rounds.

The algorithm of [31] for finding a minimum cut in a weighted graph is actually based on the $2$-respecting minimum-cut framework of [27]; where a spanning tree $T\subseteq E$ is called $2$-respecting for a cut $𝒞\subseteq E$ if $|𝒞\cap T|\le 2$. The main insight here is that a given a spanning tree $T$ that is $2$-respecting for a minimum cut $𝒞$, there are only $O(n^2)$ cuts that one needs to check to find a minimum cut, and they correspond to all pairs of edges in $T$. Originally [27], proposed a clever dynamic algorithm to calculate all these cuts quickly. In contrast, the algorithm of [31] leverages the structure of the $2$-respecting spanning tree to show that the number of potential cuts is actually much smaller; restricting attention to sub-trees, $\{T_i\}$, that are all paths and whose total size is bounded. Furthermore, when $T$ is a path the task of finding a minimum cut reduces to the following problem.

In the context of the minimum cut problem, each entry in the matrix corresponds to a cut in $G$ and can be recovered using a single cut query. We summarize some results from [31] in the following lemma, whose proof is provided in the full version of the paper.

Therefore, in order to find a minimum cut it suffices to construct a cut sparsifier and then solve the monotone matrix problem. Our main technical contribution in this section is a construction of a cut sparsifier with low adaptivity. We begin by formally defining the notion of a cut sparsifier.

We now sketch the proof of Lemma 2.16, for more details see the full version of the paper. The sparsifier construction is similar to the one in [33, 32] but modified to work in $r$ rounds. It follows the sampling framework of [13], that shows that if one samples every edge in a graph with probability proportional to its strong connectivity, then the sampled graph is a $(1\pm ϵ)$-cut-sparsifier with high probability. The algorithm is based on iteratively finding the strongest components of the graph using weight-proportional edge sampling, assigning a strength estimate to all their edges, and contracting them. It repeats this process until all vertices are contracted. Finally, it samples all the edges in the graph according to their strength estimates, and returns the sampled edges as the sparsifier.

Our algorithm improves on the round complexity of the existing constructions in two ways: the first one is the adoption of a two-round weight-proportional sampling algorithm that eliminates an $O(\log n)$ factor in the round complexity. The second improvement is in the number of contraction steps performed. The algorithm of [33, 32] uses $O(\log (nW))$ steps, where in each step strengths are approximated within factor $2$. Our algorithm uses instead $r$ steps, where each step contracts all components with strength within an $n^{(1+{\log }_{n}W)/r}$ factor. Since the maximum component strength is $O(n^{1+{\log }_{n}W})$, the algorithm can contract all the components within $r$ steps.

Our second technical contribution is an algorithm that solves the monotone matrix problem in few rounds, the proof is provided in the full version of the paper.

The algorithm for the monotone matrix problem in [31] uses a divide-and-conquer approach. At each step the algorithm reads the entire middle column $j$ of the matrix $A$ and finds the minimum value in the column. Then, it splits the matrix into two submatrices $A_L=A[1,\mathrm{\dots },j_s;1,\mathrm{\dots },j]$ and $A_R=A[j_t,\mathrm{\dots }n;j+1,\mathrm{\dots }n]$ based on the location of the minimum value in the column. The algorithm is guaranteed to find the minimum value in each column by the monotonicity property of the matrix. Finally, it is easy to verify that as the size of the problem decreases by factor $2$ in each iteration, the overall complexity of the algorithm is $\tilde{O}(n)$.

Unfortunately, the algorithm of [31] requires $O(\log n)$ rounds to complete all the recursion calls. Our algorithm instead partitions the matrix into $n^{1/r}$ blocks and then recurses on each block, which requires a total of $O(n^{1+1/r})$ queries in $r$ rounds.

To conclude this section, notice that Theorem 1.5 follows by combining Lemma 2.14, Lemma 2.16, and Lemma 2.17.