Pseudodeterministic Algorithms for Minimum Cut Problems

In this work, we investigate the design of pseudodeterministic algorithms for the well-studied problem of global minimum cut. The global minimum cut problem takes as input a weighted undirected graph $G$ on $n$ vertices and $m$ edges, and produces as output a partition of the vertices of $G$ which minimises the total weight of edges crossing the partition. This is closely related to the minimum $s$-$t$ cut problem, which produces as output a partition of vertices of $G$ such that the vertices $s$ and $t$ lie on different sides of the partition. Naively, the global minimum cut problem can be solved using $n-1$ calls to a minimum $s$-$t$ cut algorithm [18]. Thus, it was initially believed that global minimum cut is a harder variant of the minimum $s$-$t$ cut problem. Eventually, Nagamochi and Ibaraki [33] and Hao and Orlin [23] showed that global minimum cut can be solved with running time matching the best known minimum $s$-$t$ cut algorithms at the time. Karger then initiated a line of work on randomized algorithms for the global minimum cut problem [25, 28, 26], eventually culminating in a $O(m{\log }^{3}n)$ time algorithm, which is faster than the best minimum $s$-$t$ algorithms even 25 years later. Thus, global minimum cut became one of the classical examples of how randomness can lead to significantly faster and simpler algorithms. Gawrychowski et al. [11] improved a log factor in Karger’s algorithm, giving a $O(m{\log }^{2}n)$ time randomized algorithm for global minimum cut. Recently, Henzinger et al. [24] obtained an $\tilde{O}(m)$¹¹1The $\tilde{O}$ hides $\mathrm{polylog}(n)$ factors. time deterministic algorithm for global minimum cut. We note that their algorithm, while matching the runtime of randomized algorithms upto polylog factors, seems to have a high exponent in the log term and is far more complicated than Karger’s near-linear time algorithm [26].

We present a simple and efficient pseudodeterministic algorithm for the global minimum cut problem that uses, as black-box, any randomized algorithm for global minimum cut.

Our result, in conjunction with the algorithm of Gawrychowski et al. [11], immediately implies a pseudodeterministic global minimum cut algorithm with running time $O(m{\log }^{3}n\log \log n)$, which is significantly faster than the best deterministic algorithm. The relative simplicity of our algorithm is an additional advantage.

Since its introduction, pseudodeterminism has been studied in many contexts, such as query complexity [14, 6, 17], streaming algorithms [21, 4, 16], parallel algorithms [15, 2, 13], space-bounded computation [22], and more²²2For a better overview of the field, we refer the reader to the doctoral thesis of Grossman [20].. In this paper, we provide efficient implementations of our pseudodeterministic global minimum cut algorithm in the streaming, cut query and parallel models. Our pseudodeterministic algorithms are significantly more efficient than the best-known deterministic algorithms in the respective models. In fact, as we discuss below, there exist large gaps between randomized and deterministic algorithms in all these models, unlike in the sequential model.

1. 1.

   Streaming: In this model, the input graph consists of a stream of insertions or deletions of edges and their associated weights. Specifically, each stream element is either of the form insert $(e,w_e)$, where $e\in E$ and $w_e\in {\mathbb{Z}}^{+}$, or of the form delete $e$. Note that we consider streaming of simple graphs, and therefore, an edge once inserted cannot be inserted again until it is deleted. The typical goal is to compute the global minimum cut using as little space and making as few passes over this stream as possible.

   A randomized exact streaming algorithm for global minimum cut using $\tilde{O}(n)$ space and $\log (n)$ passes was shown by Mukhopadhyay and Nanongkai [31]. As far as we are aware, there is no deterministic algorithm for this problem using $O(n^{1.99})$ space and making $\tilde{O}(1)$ many passes.

1. 2.

   Cut Query: Here, access to the graph is permitted only via an oracle which takes as input a partition of the vertices into two parts and produces as output the total weight of edges which cross this partition. The goal is to compute the global minimum cut making as few queries to this oracle as possible.

   A randomized exact algorithm for global minimum cut using $\tilde{O}(n)$ many cut queries was shown by Mukhopadhyay and Nanongkai [31]. As far as we are aware, the best deterministic algorithm is a corollary of the algorithm by Grebinski and Kucherov [19] and reconstructs the entire graph using $O(n^2/\log n)$ many queries.

1. 3.

   Parallel: We consider the Common-Read-Exclusive-Write ($\mathrm{𝖢𝖱𝖤𝖶}$) Parallel Random Access Machine ($\mathrm{𝖯𝖱𝖠𝖬}$) model, where there are $p$ processors connected to a shared random access memory. An arbitrary number of processors can read from a memory cell, whereas only one processor can write on a memory cell in a single time step.

   In this model, a randomized exact algorithm for global minimum cut with $\tilde{O}(m)$ work and $\tilde{O}(1)$ depth was given by Anderson and Blelloch [3]. As far as we are aware, the only deterministic NC algorithm for this problem is by Karger and Motwani [27]. While they do not explicitly calculate the work of their algorithm, it is certainly a huge polynomial, and seems to be worse than even, say, $O(n^{10})$.

A key tool in our algorithm is built upon the isolation lemma. Introduced by Mulmuley, Vazirani, and Vazirani [32], the isolation lemma states that for any family of objects built on a ground set $E$, such as perfect matchings of a bipartite graph, if one assigns random polynomially bounded integer weights to each element of $E$, the minimum weight object, i.e., perfect matching, will be unique with high probability. Derandomizing the isolation lemma has since been a major open problem, with a long line of work on it (See e.g. [5, 8, 9, 37, 1])

Goldwasser and Grossman [15], in their pseudodeterministic NC algorithm for bipartite perfect matching, gave a pseudodeterministic algorithm for assigning edge weights to a bipartite graph such that the minimum weight perfect matching is unique with high probability. Then, using a randomized NC algorithm for minimum weight perfect matching on the input graph with their constructed edge weights, they obtain a pseudodeterministic NC algorithm for bipartite perfect matching. Anari and Vazirani [2] do the same for non-bipartite matching, and Ghosh et al. [13] for linear matroid intersection.

In this work, we follow a similar route as the algorithm of [15]. Our pseudodeterministic algorithm takes as input a weighted graph, and applies perturbations to the weights in order to make the global minimum cut of the graph unique. We mention that the previous algorithms that follow this approach in [15, 2] are slower than their randomized counterparts by a polynomial factor. Thus, ours is the first instance of this approach that preserves computational efficiency.

The implementations of our algorithm in the four models that we discussed (sequential, streaming, cut query, parallel) lose only a logarithmic factor in efficiency in all of those models. Thus, combining our algorithm with the randomized algorithms in [11, 31, 3], we obtain near optimal pseudodeterministic algorithms for global minimum cut across many models of computation. Moreover, while the isolation lemma has previously found applications in parallel [32, 8, 9, 37], space-bounded [36, 38], catalytic [1, 29] and sequential [32] models, this is the first application of isolation that we are aware of in streaming and cut query models.

We note that our exact approach can also give similar blackbox statements for the more general problem of submodular function minimisation. For succinctness, we do not state this explicitly in the paper.

The paper is organized as follows. Section 2 contains basic notation and definitions that we use throughout. Section 3 presents a pseudodeterministic algorithm for the minimum $s$-$t$ cut problem and introduces some of the key ideas that we use in this paper. Section 4 contains our pseudodeterministic global minimum cut algorithm and its analysis. Finally, Section 5 contains the details of the implementation of our algorithm in the streaming, cut query and parallel models.

Say $𝒜$ runs in time $T(n,m)$ on a graph $G$ with $n$ vertices and $m$ edges. Clearly, Algorithm 2 can be implemented such that it runs in $O(m+n+T(n,m+n))$ time. Then, Algorithm 3 can be implemented to run in $O((m+n+T(n,m+n)\log n\log \log n))$ time. Combined with the randomized $O(m{\log }^{2}n)$ time algorithm of [11], this gives us a pseudodeterministic $O(m{\log }^{3}n\log \log n)$ time algorithm for global minimum cut, thereby proving Theorem 1. This additional $\log \log n$ factor is in order to boost the success probability of $𝒜$ from $2/3$ to $1-1/\mathrm{\Omega }(\log n)$. We incur a similar cost in the other models, but it is hidden under the tilde notation.

Both Algorithm 3 and Algorithm 2 involve only the following non-trivial steps:

1. 1.

   Adding the edges $E_{\mathrm{star}}^s$ of a star graph to the graph $G$. This can be done with $\tilde{O}(n+m)$ work and $\tilde{O}(1)$ depth by simply adding $(s,v)$ for all $v\in V$ in parallel. It is easy to avoid adding a duplicate edge by maintaining a lookup table indexed by $v\in V$, indicating whether $(s,v)\in E$.

2. 2.

   Stitching a weight assignment $w^{\prime }$ with a weight assignment $w$. Our algorithm only does this when $n$ is an upper bound on ${\sum }_{e\in E}{w}^{\prime }(e)$. Thus, we simply need to replace the weight $w$ of each edge with $(n+1)\cdot w(e)+w^{\prime }(e)$. By doing this in parallel for each $e\in E$, this takes $\tilde{O}(n+m)$ work and $\tilde{O}(1)$ depth.

3. 3.

   Testing whether two cut-sets $S$ and $S^{\prime }$ are equal. There are many easy ways to do this with $\tilde{O}(n+m)$ work and $\tilde{O}(1)$ depth.

4. 4.

   Computing the weight of a cut with respect to an edge weight assignment $w$. By simply iterating over all edges in parallel, and then adding up their contribution to the cut in a tree-like fashion, this can be done with $\tilde{O}(n+m)$ work and $\tilde{O}(1)$ depth.

Say $𝒜$ takes work $W(n,m)$ and depth $D(n,m)$ on a graph with $n$ vertices and $m$ edges. With the aforementioned observations, it’s easy to see that Algorithm 2 and Algorithm 3 can be implemented with work $\tilde{O}(n+m+W(n,m+n))$ and time $\tilde{O}(D(n,m+n))$. The $\tilde{O}$ absorbs the $\log n$ factor from the binary search in Algorithm 3. Combined with the $\tilde{O}(n+m)$ work and $\tilde{O}(1)$ depth algorithm of [3], we obtain a pseudodeterministic $\tilde{O}(m)$ work and $\tilde{O}(1)$ depth parallel algorithm, thereby proving Theorem 4.

Both Algorithm 3 and Algorithm 2 involve only the following non-trivial steps:

1. 1.

   Adding the edges $E_{\mathrm{star}}^s$ of a star graph to the graph $G$. This can be done by simply suffixing the edges $E_{\mathrm{star}}^s\setminus E$ to the input stream with weights $0$. In order to do this, one needs to track the edges $E\cap E_{\mathrm{star}}^s$ in the input stream. This is easy to do using $O(n\log n)$ space since $|E_{\mathrm{star}}^s|=n$ – one can simply maintain a list of all edges of $E_{\mathrm{star}}^s$ and whether they have already appeared in the stream.

2. 2.

   Stitching a weight assignment $w^{\prime }$ with a weight assignment $w$. Our algorithm only does this when $n$ is an upper bound on ${\sum }_{e\in E}{w}^{\prime }(e)$. Moreover, our algorithm can always compute $w^{\prime }(e)$ for any edge $e$ given only the endpoints of $e$. Thus, every time we encounter an edge $e$ in the stream with edge $w(e)$, we can simply change its weight to $w(e)\cdot (n+1)+w^{\prime }(e)$. This part implicitly requires space to store the information to compute $w^{\prime }$, which is just $s$, if $w^{\prime }=w_s$, or $x$ and $s$, if , or the cut-set $S$ along with vertices $s$ and $t$ if $w^{\prime }$ is $w_1$ or $w_2$. Storing the cut-set $S$ is the most expensive and only requires $O(n\log n)$ space.

3. 3.

   Testing whether two cut-sets $S$ and $S^{\prime }$ are equal. Since we have no time restriction in the streaming model, once we have the sets $S$ and $S^{\prime }$ stored using $O(n\log n)$ space, this is completely trivial to do using no additional space.

4. 4.

   Computing the weight of a cut $(S,T)$ with respect to a weight assignment $w^{\prime }$. In our algorithm, we only need to do this when , and the algorithm already knows $x$. Thus, this is easy to do: we maintain $W$, initialised to $0$. Every time an edge $e$ crossing the cut $(S,T)$ is added to the graph in the stream, we modify $W=W+w^{\prime }(e)$, and every time an edge $e$ is deleted from the graph, we modify $W=W-w^{\prime }(e)$. The only space required here is to store $x$ and $W$. This requires $O(\log n)$ space.

Let $𝒜$ be a streaming algorithm that uses $S(n,m)$ space and makes $P(n,m)$ passes over the stream. With the aforementioned observations, Algorithm 2 and Algorithm 3 can be implemented with space $\tilde{O}((S(n,m)+n)$ and $O(P(n,m)\cdot \log (n))$ passes over the stream. Combined with the $\tilde{O}(n)$ space and $O(\log n)$ passes algorithm of [31], we obtain a pseudodeterministic $\tilde{O}(n)$ space and $O({\log }^{2}n)$ passes streaming algorithm, thereby proving Theorem 2.

For cut query algorithms, the argument is largely very simple, since the only restriction in the model is on queries to the graph and not on any computational aspect. The only non-trivial implementation question is about how to stitch weights $[w,w^{\prime }]$ in the cut query model. Formally, given a cut oracle $𝒪$, where $𝒪(S)=w({\mathrm{cut}}_G(S))$, we want to design an oracle ${𝒪}^{\prime }$ where ${𝒪}^{\prime }(S)=[w,w^{\prime }]({\mathrm{cut}}_G(S))$. This is easy to do because of our choices of stitched weights and graphs. In both Algorithm 2 and Algorithm 3, $w^{\prime }({\mathrm{cut}}_G(S))$, for any $\mathrm{\varnothing }⊊S⊊V$, can be computed given only $S$, and the parameters of the weight function $w^{\prime }$. Assume $s\in S$:

1. 1.

   $w_s({\mathrm{cut}}_G(S))$ is equal to $n-|S|$.

2. 2.

   is equal to .

3. 3.

   Let $\widehat{S}$ be the cut-set with respect to which $w_1$ is defined, such that $s\in \widehat{S}$. Then $w_1(\widehat{S})=|(V\setminus S)\cap (V\setminus \widehat{S})|$. The same argument holds for $w_2$ and $t$.

Thus, the oracle ${𝒪}^{\prime }$ can simply return as its answer ${𝒪}^{\prime }(S)=𝒪(S)\cdot (n+1)+w^{\prime }({\mathrm{cut}}_G(S))$.

Let $𝒜$ be a cut-query algorithm that makes $C(n,m)$ many cut queries. With the aforementioned observation, it’s easy to see that Algorithm 3 and Algorithm 2 can be implemented such that they require $O(C(n,m)\cdot \log n)$ many queries. Thus, combined with the algorithm of [31], we obtain an algorithm which requires $\tilde{O}(n)$ many cut queries, thereby proving Theorem 3.