Space Complexity of Minimum Cut Problems in Single-Pass Streams

The key method so far for solving minimum cut with low-memory is the usage of cut sparsifiers. The notion of cut sparsifiers was introduced by Benczur and Karger [7] and has been extremely influential. Given a weighted graph $G=(V,E,w)$ with $n=|V|$ vertices and $m=|E|$ edges, and polynomially bounded edge weights $w:E\to {ℝ}_{+}$, together with an accuracy parameter $\epsilon >0$, a cut sparsifier of $G$ is a sparse subgraph $H$ on the same vertex set $V$ but with (possibly) different edge weights such that the weight of every cut in $G$ is $(1+\epsilon )$-approximated by the weight of the corresponding cut in $H$. For two sets $S,T\subseteq V$, we use $E(S,T)=\{(u,v)\in E:u\in S,v\in T\}$ to denote the set of edges between $S$ and $T$ in graph $G$ and $w_G(S,T)={\sum }_{e\in E(S,T)}{w}_e$ to denote the total weight of edges between $S$ and $T$ in graph $G$. Formally, we have the following definition,

Specifically, [7] shows that a cut sparsifier always exists with $O(n\log n/{\epsilon }^2)$ edges. This bound was improved to $O(n/{\epsilon }^2)$ edges by [6] and [1, 2, 11] proved a lower bound of $\mathrm{\Omega }(n(\log n)/{\epsilon }^2)$ bits (even in the case when the cut-sparsifier $H$ is a not necessarily a subgraph of $G$). The existence bound was also extended to the stronger notion of spectral sparsifiers [46, 47, 45, 6], where the quadratic form associated with the Laplacian of graph $H$ provides a $(1+\epsilon )$-approximation to that of $G$. Let $L_G$ denote the Laplacian matrix of graph $G$. For every subset $S\subseteq V$, let $x_S$ be the binary indicator vector of $S$ such that $x_i=1$ if $i\in S$ and $x_i=0$ if $i\notin S$. Then we have $x_S^{\top }{L}_G{x}_S=w_G(S,V\setminus S)$. The definition of the spectral sparsifier extends the assumption that $x$ is a binary vector to an arbitrary vector.

This construction has had a tremendous impact on cut problems in graphs, see, e.g., [7, 8, 30, 44, 35]. However, for very small values of $\epsilon$, the $1/{\epsilon }^2$ dependence in cut sparsifiers may be prohibitive on large-scale graphs. Motivated by this, the work of [2] relaxed the cut sparsification problem to that of outputting a data structure ${\mathrm{sk}}_G$ such that given any fixed cut $S\subseteq V$, the value of ${\mathrm{sk}}_G(S)$ is within a $(1+\epsilon )$ factor of the cut value of $S$ in $G$, with probability at least $2/3$¹¹1This can be amplified to high probability, which we define to mean with probability at least $1-1/\mathrm{poly}(n)$. This is done by independently repeating the data structure $O(\log n)$ times and outputting the median estimate. This also lets us estimate the cut value for $\text{poly}(n)$ cuts simultaneously.. This relaxed notion of the problem is called the “for-each” model, which should be contrasted with the previous “for-all” model of cut and spectral sparsification.

Surprisingly, [2] showed that such a data structure exists for cut sparsification with $\mathrm{poly}(n)$-bounded integer edge weights of size $\tilde{O}(n/\epsilon )$²²2Throughout we use $\tilde{O}(\cdot )$ to hide $\text{polylog}(n)$ factors., which is optimal up to polylogarithmic factors. In a follow-up work of [24], the authors extended the $\tilde{O}(n/\epsilon )$ upper bound to the for-each model for spectral sparsifiers. Another very interesting work is  [14], which shows that such a sketch can be chosen as a reweighted subgraph of $G$. We specifically deal with these graphical for-each sparsifiers:

In a line of work, see, e.g., [36, 27, 28], efficient algorithms for sparsifiers in the for-all model in a graph stream were constructed. The state-of-the-art work [28] gives a single-pass algorithm for spectral sparsification in dynamic streams which uses space $\tilde{O}(n/{\epsilon }^2)$.

However, it was not known how to construct a for-each sketch for cut sparsification in a stream in better than $\tilde{O}(n/{\epsilon }^2)$ space, which follows from computing a for-all sparsifier. A natural question is whether we can implement a streaming algorithm that computes a for-each sparsifier with space matching the $\mathrm{\Omega }(n/\epsilon )$ offline lower bound that holds for for-each sparsification [2].

If we can answer this question in the affirmative, we can also get a better space bound for the approximate minimum cut problem. It is well-known that there are only poly$(n)$ $O(1)$-approximate minimum cuts³³3When we say a cut is an $\alpha$-approximate minimum cut, we mean that its cut value is at most $\alpha$ times the minimum cut value. in a graph. So we can run a for-all cut sparsification algorithm in a stream with $\epsilon =\mathrm{\Theta }(1)$ in $\tilde{O}(n)$ space and obtain a candidate set of poly$(n)$ cuts containing the minimum cut. In parallel, we estimate the value of each cut using a for-each sparsifier with failure probability $1/\text{poly}(n)$. The smallest cut out of the candidate cuts will be a $(1+\epsilon )$-approximate minimum cut. Thus, the space complexity is just $\tilde{O}(n)$ plus that of maintaining a for-each sparsifier in a stream. However, the existing algorithms for computing for-each sparsifiers are not streaming algorithms. Motivated by the existence of a for-each sketch in $\tilde{O}(n/\epsilon )$ bits of space, one may wonder if it is possible to obtain a $(1+\epsilon )$-approximation to the minimum cut in $\tilde{O}(n/\epsilon )$ space in a single-pass stream.

We also note that an exact global minimum cut streaming algorithm exists in $\tilde{O}(n)$ space with two passes for simple graphs [5] (see also [43]) and $\log n$ passes for weighted graphs [38].

We know that finding the minimum cut exactly in single-pass adversarial streams needs $\mathrm{\Omega }(n^2)$ space [52]. We need an additional pass to get the exact minimum cut in $\tilde{O}(n)$ space. However, many streaming applications require solving the problem in exactly one pass because the stream cannot be stored.

Thus, to surpass the $\mathrm{\Omega }(n^2)$ barrier of adversarial streams in one pass, we consider a relaxation known as random-order streams and ask whether we can find the minimum cut exactly in $o(n^2)$ space in this setting. In this model, the graph can still be chosen adversarially, but its edges arrive in the stream in a random order.

The motivation for studying this model stems from the fact that real-world data is typically not adversarial. Adversarial streams are adversarial in both their input and arrival order, while random-order streams relax the arrival order, making them more representative of real-world data. Additionally, the random-order streaming model may help explain the empirical performance of certain heuristics.

This model was first studied by [39] for sorting in limited space. Many subsequent works have studied problems in random-order streams [21, 26, 12, 37, 42, 16, 13], some of which show a clear separation between the adversarial and random-order models.

One notable line of work focuses on maximum matching within this model [33, 19, 32, 3, 18, 9, 4, 22]. The best-known upper bound in the random order model [4] gets a slightly better than $2/3$-approximation in semi-streaming space, which is better than the best possible $\frac{1}{1+\ln 2}\approx 0.59$-approximation in the adversarial model due to the lower bound of [25], showing another separation between adversarial and random-order streams.

Motivated by this, we study the minimum cut problem in the random-order model and ask the following question:

This work resolves the above questions with matching algorithms and lower bounds. We also carefully optimize the running time and update time of our algorithms. We also obtain several additional results, which we outline in Section 3.

Given $G(V,E,w)$ as an electrical network on $n$ nodes in which each edge $e$ corresponds to a link of conductance $w_e$ (i.e., a resistor of resistance $1/w_e$), the effective resistance of an edge $e$ is the potential difference induced across it when a unit current is injected at one end of $e$ and extracted at the other end of $e$. Equivalently it is equal to $R_{\text{eff}}^G={\chi }_{u,v}^{\top }{L}_G^{†}{\chi }_{u,v}$, where $L_G^{†}$ denotes the pseudoinverse of the Laplacian of graph $G$ and ${\chi }_{u,v}:=1_u-1_v$.

In the all-pairs effective resistance problem, we are required to output a data structure, which with high probability can generate effective resistance values for each of the $n^2$ pairs of vertices, or a $(1+\epsilon )$-approximation of each of the $n^2$ pairs of values in the $(1+\epsilon )$-approximate version of the problem. Note that the data structure implicitly represents these $n^2$ values and responds with one such value on a given query pair.

Short cycle decompositions are a recent algorithmic tool for graph sketching problems introduced by Chu et al. [14].

The main contribution of [14] to spectral sparsification is in proving the following claim:

As a high-level overview, the short-cycle decomposition is key as a degree-preserving sparsification method. Given each cycle, we can label them numerically in order and sample either all the odd or all the even labeled edges, each with $1/2$ probability. Previous works on “for-each” sparsifiers [2, 24] used a recursive expander decomposition and subsampling at each level, with the main issue being that the degrees were not well-preserved. This issue was solved by explicitly storing the degrees of the graph, causing their spectral sparsifier data structure to no longer be a graph. The work of [14] circumvents this issue with the short-cycle decomposition by constructing subsampled graphs that exactly preserve their vertex degree.

Note that [14] already gives a graphical spectral sparsifier with $\tilde{O}(n/\epsilon )$ edges and bits of working memory using a basic brute-force search for cycle decomposition. However, its runtime for construction is $O(mn)$, which is prohibitively slow as a subroutine. On the other hand, later work by Parter and Yogev [41] shows a deterministic algorithm to compute $(O(n\log n),O({\log }^{2}n))$ short-cycle decompositions. This combined with 8 will allow us to design an algorithm in $m^{1+o(1)}$ time which returns a $(1+\epsilon )$-spectral sparsifier which is a reweighted graph with $\tilde{O}(n/\epsilon )$ edges. This gives near-optimal parameters except for a required $m^{1+o(1)}$ bits of working memory. However, in Section 4.1, we show that we can implement this subroutine so that it is guaranteed to use only $\tilde{O}(m)$ working memory, achieving near-optimal results in both working memory usage and running time.

While we resolve several gaps between the upper and lower bounds, we discuss a remaining open problem. There exist fully dynamic streaming algorithms for approximate minimum cut using $\tilde{O}(n/{\epsilon }^2)$ space where the stream is allowed to both add or delete edges. From Theorem 12, we know that algorithms solving approximate minimum cut in insertion-only streams must use $\mathrm{\Omega }(n/\epsilon )$ space. Therefore, the space complexity of approximate minimum cut in a dynamic stream lies somewhere within these two values, and we believe resolving this gap is a problem of theoretical interest.

We do not have an exact conjecture about this, but we provide an alternative and fully self-contained proof to Theorem 12 in the full version of the paper [17], for which the techniques could help prove a lower bound for the fully dynamic case.

Our algorithm uses the following result in [14] as a subroutine.

As pointed out by the work of [41], in the above algorithm, the extra $n^{o(1)}$ factor in the number of edges is due to the nearly-linear time short cycle decomposition used in the whole algorithm. We use the simpler and improved short-cycle decomposition algorithm of [41], which outputs in $m^{1+o(1)}$ time a collection of edge-disjoint cycles of length $O({\log }^{2}n)$ that cover all but $O(n\log n)$ edges of the graph. Naïvely, the algorithm is also implemented in $m^{1+o(1)}$ space, but we show that a simple modification achieves near-linear space, as follows:

For the purposes of a faster runtime, we consider only sampling (and reweighting) a fraction of edges during the stream. Existing online leverage score sampling methods allow us to choose edges in an online stream without retracting our choices such that our final graph has $\tilde{O}(n/{\epsilon }^2)$ edges and is a spectral-sparsifier of the original graph. Indeed, let $B_n\in {ℝ}^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)\times n}$ be the vertex edge incidence matrix of an undirected, unweighted complete graph on $n$ vertices, where the $e$-th row $b_e$ for edge $e=(u,v)$ has a $1$ in column $u$, a $(-1)$ in column $v$, and zeroes elsewhere. Then for an arbitrary undirected graph $G$, we can write its vertex edge incidence matrix $B=S{B}_n$ where $S\in {ℝ}^{\left(\genfrac{}{}{0pt}{}{n}{2}\right)\times \left(\genfrac{}{}{0pt}{}{n}{2}\right)}$ is a diagonal matrix with entry $\sqrt{w_e}$ in the $e$-th diagonal entry where $w_e$ is the weight of edge $e$. It is well-known that the Laplacian matrix $L$ of graph $G$ can be written as $L=B^{\top }B$. Hence, if we can sample a subset of the rows of $B$ to form a new matrix $C$ (which corresponds to a subset of the edges in $G$) such that for every $x$, ${\Vert Bx\Vert }_2{\approx }_{\epsilon }{\Vert Cx\Vert }_2$, we then have $x^{\top }Lx{\approx }_{\epsilon }{x}^{\top }{C}^{\top }Cx$ so that the subgraph $H$ corresponding to $C$ is a $(1+\epsilon )$-spectral sparsifier of $G$. For more details, we refer the reader to [27, 15]. Formally, we have the following lemma.

Our algorithm is presented in Algorithm 1, which is based on the merge-and-reduce paradigm (see, for example, [10]) and uses an additional factor of $\mathrm{polylog}(n)$ space. At a high level, our algorithm maintains a number of blocks of edges ${𝐁}_0,{𝐁}_1,\mathrm{\dots }{𝐁}_{\log (n/\epsilon )}$, each with size ${𝗆}_{\mathrm{𝗌𝗉𝖺𝖼𝖾}}=\tilde{O}(n/\epsilon )$. The most recent edges are stored in ${𝐁}_0$; whenever ${𝐁}_0$ is full, the successive non-empty blocks ${𝐁}_0,\mathrm{\dots },{𝐁}_i$ are merged and reduced to a new graph with ${𝗆}_{\mathrm{𝗌𝗉𝖺𝖼𝖾}}$ edges, which will be stored in ${𝐁}_{i+1}$. Next, we show the correctness of our algorithm. Following a similar argument in [10], we first show the following lemma.

Our main application of Lemma 10 is the one-pass streaming algorithm for a $(1+\epsilon )$-approximation to the minimum cut. To achieve this, first recall that we can get a $(1+\epsilon )$ for-all sparsifier of $G$ in a one-pass stream in nearly-linear time, using $\tilde{O}(n/{\epsilon }^2)$ bits of space (Lemma 4).

The next lemma bounds the number of approximate minimum cuts.

Motivated by [2], we run our algorithm in Lemma 10 along with the streaming for-all sparsifier algorithm $\mathrm{𝖠𝖫𝖦}$ in Lemma 4 with accuracy parameter ${\epsilon }^{\prime }=O(1)$. Suppose that the output of $\mathrm{𝖠𝖫𝖦}$ is $H$. We then use $H$ to find the cuts that have a size less than $1.5$ times that of the minimum cut value (which can be done in $\mathrm{poly}(n)$ time, see, e.g., [29]). Then, since the number of these approximate minimum cuts is $O(n^3)$, using our $(1+\epsilon )$ for-each sparsifier, we can get a $(1+\epsilon )$-approximation to each of these cut values with high probability after taking a union bound. Picking the cut with the minimum value gives us a $(1+\epsilon )$-approximate minimum cut.

To prove this lower bound, we consider the $k$-edge-connectivity problem as follows. The edge-connectivity of a graph is the minimum number of edges that need to be deleted to disconnect the graph. The $k$-edge-connectivity problem asks whether the edge connectivity of a graph is or $\ge k$. The work of [49] shows that any deterministic algorithm that solves the $k$-edge-connectivity problem in insertion-only streams needs $\mathrm{\Omega }(kn\log n)$ bits of space. We note that the proof in [49] also works for randomized algorithms with success probability at least $1-1/n$, which implies a lower bound of $\mathrm{\Omega }(kn)$ bits of space for any randomized algorithm with constant probability of success.

We now prove the randomized and deterministic lower bounds of Theorem 12.

Another application of our streaming algorithm from Lemma 10 is calculating all-pairs effective resistances in graph streams. Suppose we have a $(1+\epsilon )$ for-each spectral sparsifier $H$ of the original graph $G$. Then, we may hope it will be helpful to approximate the pseudoinverse of $G$. In fact, in the work of [24], it has been shown that if we have a $(1+\epsilon )$ for-each spectral sparsifier, we can use it to generate an effective resistance sketch in near-linear time, which can compute the all-pairs effective resistances in $\tilde{O}(n^2/\epsilon )$ additional time (Algorithm 8 in [24]). From this, we immediately see the correctness of our Corollary 11.

We will use the algorithm in Lemma 4 (for-all sparsifier in a stream) as a subroutine. The whole algorithm is given in Algorithm 2. Below, we first give a high-level explanation of our algorithm. We first consider the case when the minimum cut size is $s=\mathrm{\Omega }(\log n)$. Since we are now considering the random-order model, a prefix of the edges gives us partial information about the cut sizes. Let $H$ be the subgraph of $G$ which is formed by a prefix of the edges of the stream where $|H|\approx \frac{|G|\log n}{s}$ and $|G|$, $|H|$ are the number of the edges in $G$ and $H$ respectively. By a Chernoff bound, one can show that with high probability, for every subset $S\subset V$, $w_H(S,V\setminus S)$ is a small constant approximation to $w_G(S,V\setminus S)$. $H$ might be too large to store in memory, so we store $H_1$, a $(1+\epsilon )$-for-all sparsifier of $H$, during the stream (we will decide $\epsilon$ later). Therefore, using the graph $H_1$, we know all cuts in $G$ whose cut size is within a factor of $1.1$ of the true minimum cut of $G$. After this step, when a new edge $e\in G\setminus H$ arrives, we can use graph $H_1$ to check whether $e$ belongs to some $1.1$-approximate minimum cut in $G$, and if so, we save this edge (from Lemma 30 we know that the total number of these edges saved is at most $O(n)$). The next question is how to estimate the exact value of these $1.1$-approximate cuts in $H$. The crucial observation is since the minimum cut size of $H$ is an integer and is at most $\mathrm{\Theta }(\log n)$, we can set the approximation parameter $\epsilon =1/{\log }^{2}n$ for $H_1$. This gives the exact value of $w_H(S,V\setminus S)$ if $S$ and $V\setminus S$ is a constant-approximate minimum cut in $G$ (since the error is at most ). Putting these things together, after the stream, we can enumerate all $1.1$-approximate minimum cuts and obtain their exact values, thus getting the exact minimum cut value.

The remaining case to handle is when the minimum cut size is $O(\log n)$. Similarly, in this case, setting $\epsilon =1/{\log }^{2}n$ will give us the exact value of the minimum cut. Finally, we do not know the value of $s$, so we will try all powers of $2$ for it. Note that we do not need the exact value; a $2$-approximation to $s$ will suffice. The detailed description of the algorithm is given in Algorithm 2.