Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions

Consider an undirected graph with m edges on n vertices. A minimum cut (or min-cut) of the graph is a minimum weight set of edges whose removal partitions the vertices into two connected components. More generally, a minimum k-cut (or min-k-cut) is a minimum weight set of edges whose removal partitions the vertices into at least k connected components; a min-cut is simply a min-k-cut for \(k=2\). Min-cut and min-k-cut are fundamental problems in combinatorial optimization and network reliability, and an impressive body of work has been devoted to designing algorithms for these problems. Perhaps the simplest, and one of the most elegant, among them is the randomized contraction algorithm of Karger [18]. For min-cut, this algorithm selects edges at random with probability proportional to their weight (uniformly, if the graph is unweighted) and unifies their endpoints (called edge contraction) until only two vertices remain. The edges that survive at this stage are then output by the algorithm. Karger argues that the algorithm returns a min-cut with probability \(\Omega (1 / n^2)\), which implies that a min-cut can be found with high probability by running \(O(n^2 \log n)\) independent instances of the algorithm.¹ For min-k-cut, the algorithm is exactly identical, except that it terminates when k vertices are left, and outputs all the surviving edges. In this case, the probability of returning a min-cut is \(\Omega (1 / n^{2k-2})\), which can be similarly boosted by running \(O(n^{2k-2} \log n)\) independent instances of the algorithm.

Unfortunately, performing these independent runs can take \(\Omega (n^4)\) time for the min-cut algorithm and \(\Omega (n^{2k})\) time for min-k-cut, since the number of edges m can be \(\Omega (n^2)\). In a later work, Karger and Stein [20] proposed a branching approach called recursive contraction to significantly speed up this scheme. This algorithm exploits the fact that the probability of contracting a min-cut edge is rather small initially, and only increases in the later stages of the contraction algorithm. So, they proposed to run a single branch of the contraction algorithm until \(\lceil n / \sqrt {2} \rceil\) vertices remain, at which stage two identical copies of the partially contracted graph are created and independent recursive runs of the branching algorithm are performed on these copies. While it does take time to create and work with these extra copies, the total number of edges in the graph decreases fast enough that the branching algorithm runs in \(O(n^2 \log n)\) time and returns a min-cut with probability \(\Omega (1 / \log n)\). Using \(O(\log ^2 n)\) independent runs, one can now obtain a total running time of only \(O(n^2 \log ^3 n)\). With slight modifications, this algorithm can instead return a min-k-cut with high probability in \(O(n^{2k-2} \log ^3 n)\) time, and this min-k-cut algorithm remains the fastest one known for any constant \(k \gt 2\) when the edges have arbitrary weights.

A hypergraph H consists of a vertex set V and a set of hyperedges E. Each hyperedge \(e \in E\) is itself an arbitrary subset of vertices. The size of a hyperedge e is \(|e|\), the cardinality of its vertex set. The weight of a hyperedge e is denoted \(w(e)\). For a subset of hyperedges S, let \(w(S)\) denote the total weight of hyperedges in the subset. The rank r of the hypergraph H is the maximum size of a hyperedge, i.e., \(r = \max _{e \in E} |e|\). A graph is simply a hypergraph of rank 2. Accordingly, we may say a hyperedge e is incident to a vertex v if \(v \in e\). We generally use the notation \(p = \sum _{e \in E} |e|\) to denote the total size of all hyperedges in H. Finally, we define the order of H as the number of vertices \(|V|\). As before, a minimum cut (or min-cut) is a minimum weight set of hyperedges whose removal partitions the vertices into at least two connected components, and a minimum k-cut (or min-k-cut) is a minimum weight set of hyperedges whose removal partitions the vertices into at least k connected components.

A natural approach for computing min-cuts and min-k-cuts in hypergraphs is to try applying the (non-branching) randomized contraction approach of Karger [18] described above. We let \(H / e\) denote the contraction of hyperedge e in hypergraph H, accomplished by unifying e’s endpoints and removing hyperedges that now have size 1. Unfortunately, even if hyperedges are unweighted, contracting a hyperedge chosen uniformly at random may destroy a min-cut with fairly high probability when the hyperedges have variable sizes. Indeed, Kogan and Krauthgamer [24] show that this natural strategy finds a min-cut with probability exponentially small in the rank r. Recently, Ghaffari, Karger, and Panigrahi [12] showed how to achieve Karger’s \(\Omega (1 / n^2)\) probability of success by biasing the selection of hyperedges away from those of large size. Chandrasekaran, Xu, and Yu [6] refined this strategy and generalized it to work for k-cuts as well. This leads to randomized algorithms for min-cut and min-k-cut that run in \(O(pn^2 \log ^2 n)\) and \(O(pn^{2k-1} \log n)\) time, respectively. This latter result was the first polynomial time algorithm for minimum k-cut in hypergraphs for arbitrary constant k, and it remains the fastest result to date. In particular, no polynomial time deterministic algorithm is known for any \(k \gt 3\). In contrast, there are deterministic \(O(pn + n^2 \log n)\) time algorithms for the min-cut problem in arbitrary hypergraphs [23, 25] and an \(O(pmn^3)\) time algorithm for \(k=3\) [32] using other techniques.

Hence, it is reasonable to ask whether we can generalize the branching contraction approach of Karger and Stein [20] to hypergraphs as well, to yield faster randomized algorithms for the min-cut and min-k-cut problems. There appear to be two major barriers to doing so.

First, the analysis of Karger and Stein’s algorithm depends upon the branching occurring at precisely chosen moments determined by the number of vertices in the partially contracted graph. If one branches too early, then there are too many large graphs in the recursive calls, and the running time increases. If one branches too late, then it decreases the probability of a min-cut surviving beyond the branching point and to the end of a run of the algorithm. When attempting to run the branching algorithm on a hypergraph, there is a risk of contracting a very large hyperedge and skipping right past one or more of these carefully selected branching points. Thus, it appears we cannot select the branching orders in advance of our randomized contractions, and we need a smoother procedure that performs branches based on which hyperedges we are contracting.

The second barrier to generalizing Karger and Stein’s algorithm concerns the total size p of hyperedges in an arbitrary hypergraph. While we can easily see \(p = O(n^r)\) in hypergraphs of rank r, the total size could be much larger when the rank is not fixed. Any generalization of Karger and Stein’s algorithm to hypergraphs must be careful to minimize the time spent interacting with hyperedges during contractions, especially in later stages of the algorithm when the number of hypergraph copies is large.

We present a new randomized branching framework for hypergraphs, where instead of branching at fixed graph orders, we probabilistically decide whether to branch before each contraction based on the size of the hyperedge we (randomly) select to contract. Our framework allows us to derive new randomized algorithms for computing min-cuts and min-k-cuts in hypergraphs.

For hypergraphs of arbitrarily rank, we show the following result:

This result improves upon the best randomized running times for both problems due to Chandrasekaran et al. [6] by a factor of \(\widetilde{\Omega }(pn / m)\), which is at least \(\widetilde{\Omega }(n)\) and at most \(\widetilde{O}(n^2)\). ² For \(k \gt 2\), this yields the fastest algorithm for the min-k-cut problem to date. (For \(k=2\), i.e., the min-cut problem, the best running time is \(O(pn + n^2 \log n)\) [23, 25] due to deterministic algorithms. See Section 1.6 for more details.)

Dense Hypergraphs. Since the number of hyperedges m can be \(\Omega (n^r)\), the above result yields running times of \(O(n^{r+2} \log ^3 n)\) for min-cut and \(O(n^{r+2k-2} \log ^2 n)\) for min-k-cut (\(k \ge 3\)) for dense hypergraphs of constant rank r. We improve on these results by the showing that for any constant rank r:

For both minimum cut and minimum k-cut, these time bounds improve upon the best ones known for sufficiently dense hypergraphs of rank \(r \gt 2\).

Along with studying randomized contractions for hypergraph min-cut, Ghaffari, Karger, and Panigrahi [12] also initiated the study of minimum hedge-cuts. A hedgegraph \(H = (V, E)\) consists of a collection of vertices V and a collection of disjoint hedges E, each of which is a subset of edges over the vertex set V. A hedge-cut is a collection of hedges whose removal separates H into at least two components; a hedge-k-cut is a hedge-cut that separates H into at least k components. A min-hedge-cut or min-hedge-k-cut is one of minimum total hedge weight. Ghaffari, Karger, and Panigrahi [12] provide a randomized polynomial time approximation scheme and an exact quasi-polynomial time algorithm for computing a min-hedge-cut. The span of a hedge is the number of connected components in the subgraph induced by its edge set. The randomized contraction result of Chandrasekaran, Xu, and Yu [6] for hypergraph k-cut is actually a special case of a randomized algorithm they give for hedgegraphs, where every hedge has span bounded by a constant s. (Note that a hypergraph is simply a hedgegraph of unit span.) Their general algorithm runs in \(O(mpn^{ks + k - s} \log n)\) time where m denotes the number of hedges and p their total size.

Our results for computing min-cuts and min-k-cuts in hypergraphs extend to hedgegraphs of bounded span. With high probability, we can find a min-hedge-cut in \(O(m^2 n^{s+1} \log ^2 n)\) time and a min-hedge-k-cut in \(O(m^2 n^{(s+1)(k-1)} \log ^2 n)\) time, improving upon known results for all \(k \ge 2\) and \(s \ge 2\). Let the rank of a hedgegraph be the maximum number of vertices incident to edges in any one hedge. For constant rank r, we can find a min-hedge-k-cut with high probability in \(O(p + n^{(s+1)(k-1)} \log ^3 n)\) time if \(r = (s+1)(k-1)\) or \(O(p + n^{\max \lbrace r, (s+1)(k-1)\rbrace } \log ^2 n)\) time otherwise.

As mentioned above, our algorithm relies on probabilistic branching instead of branching at fixed graph orders like in the original method of Karger and Stein [20]. Instead of explicitly biasing away from larger hyperedges like in previous work [6, 12], we pick hyperedges to contract with probability proportional to their weight. Before contraction, however, we branch with a probability that is dependent on the size of the hyperedge we just selected. These probabilities are carefully selected so that the total probability of branching is at least as high as the probability of contracting an edge in the min-cut. Intuitively, the expected number of min-cuts discovered by our algorithm at the bottom of its branches ends up being at least 1. Through a relatively straightforward inductive argument, we prove that any one run of our algorithm returns a min-cut with probability at least \(\Omega (1/\log n)\). In fact, the analysis of our algorithm is arguably simpler than that given for Karger and Stein’s [20], and we give a probability bound that is actually tight for min-cut in graphs. Our high-level algorithm and the analysis bounding its probability of success appear in Section 2.

To give our specific running time bounds, we need to perform hyperedge contractions efficiently. We first consider arbitrary rank hypergraphs. In earlier work [6, 12], the contraction of a hyperedge e involved going through the incidence list of each vertex in e so that all the incidences could be replaced with a single vertex representing the contracted edge e. This process takes \(\Theta (m\cdot |e|)\) time in the worst case, so the running time of contraction increases with \(|e|\). Unfortunately, our algorithm is also more likely to branch when \(|e|\) is large, increasing our chances of performing another expensive contraction in the future. Therefore, instead of spending \(\Theta (m\cdot |e|)\) time checking incidences, we essentially make brand new copies of what remains of each edge after contraction in \(O(m(n-|e|+1))\) time so contractions that are more likely to cause branching are also cheaper to perform. We describe the implementation for arbitrary rank hypergraphs in Section 3.

For hypergraphs of constant rank r, we only make copies of the hypergraph when branching, and we otherwise perform contractions using a similar procedure as that given by Karger and Stein [20] for graphs. Specifically, we explicitly merge new parallel hyperedges after every contraction to guarantee we never store more than \(O(n^r)\) hyperedges at a time. We also generalize their edge selection procedure to select and contract a hyperedge in \(O(n^{r-1})\) time. Our implementation for constant rank hypergraphs appears in Section 4.

For hedgegraphs, randomly contracting a hedge incident to x vertices induces a branch with the same probability as contracting a hyperedge of size x. The key difference increasing the running time for hedgegraphs is that we might create more branches overall, because a hedgegraph only shrinks by \(x-s\) vertices if the contracted hedge has span s. Note that s can be as large as \(x/2\) in general, thus guaranteeing a reduction of only \(x/2\) vertices, whereas shrinking a hyperedge of size x reduces the number of vertices by \(x-1\). In addition, we need to maintain information about how the components of hedges share vertices to perform fast hedge contractions, and maintaining this information incurs additional running time. For simplicity, we stick to hypergraph min-cut and min-k-cut in most of the article before giving the necessary details for our extensions to hedgegraphs in Section 5.

We give a brief survey of what is known about computing minimum cuts and k-cuts beyond the approaches of Karger and Stein [18, 20]. Nagamochi and Ibaraki [27] gave the first min-cut algorithm for graphs that does not perform repeated computations of minimum \(s,t\)-cuts. Their approach was later refined to give \(O(mn + n^2 \log n)\) deterministic algorithms for the problem, and this running time remains the best known among deterministic algorithms [26, 29]. This running time can be improved to \(O(m + \lambda n^2)\) [26] in unweighted graphs with min-cut value \(\lambda\) and to \(O(m\log ^{12} n)\) in simple unweighted graphs [22]. The randomized \(O(n^2 \log ^3 n)\) time algorithm of Karger and Stein [20] improves upon the weighted edge result for graphs that are not too sparse. By applying other techniques, Karger [19] further improved the best randomized running time to \(O(m \log ^3 n)\).

When k is part of the input, the min-k-cut problem is NP-hard [13]. However, Goldschmidt and Hochbaum [13] were still able to give a deterministic \(n^{O(k^2)}\) time algorithm for the problem when k is a constant. Their work was followed by a series of deterministic algorithms [16, 17, 31] that led to an \(\widetilde{O}(n^{2k})\) time algorithm due to Thorup [30]. In concurrent work to our own, Chekuri, Quanrud, and Xu [8] improved this running time to \(\widetilde{O}(mn^{2k-3})\). This was further improved to \(O(k^{O(k)} n^{(2\omega /3+o(1))k})\) by a recent work of Gupta, Lee, and Li [14], where \(\omega\) is the matrix multiplication constant. For small k, the result also gives a faster randomized algorithm in time \(\widetilde{O}(k^{O(k)}n^{k+\lfloor {(k-2)/3}\omega +1+((k-2) \text{ mod } 3)}W)\), where all weights are bounded by W. For unweighted graphs and \(k\in [8,n^{o(1)}]\), this improves upon the randomized \(O(n^{2k - 2} \log ^3 n)\) time algorithm of Karger and Stein [20], while the latter still remains the state-of-the-art for weighted graphs.

The situation in hypergraphs is a bit different. Queyranne [28] gave the first non-trivial algorithm for min-cut in hypergraphs, and it was later improved by Klimmek and Wagner [23] and Mak and Wong [25] to run in \(O(np + n^2 \log n)\) time. Chekuri and Xu [9] improved the running time for unweighted hypergraphs with min-cut value \(\lambda\) to \(O(p + \lambda n^2)\). All of these algorithms are deterministic. In fact, all the randomized algorithms mentioned above are actually slower at computing min-cuts than these deterministic algorithms, with the aforementioned exception of our \(O(p + n^r)\) time algorithm for sufficiently dense hypergraphs of constant rank.

For \(k=3\), there exists a deterministic \(O(pmn^3)\) time min-k-cut algorithm due to Xiao [32, Theorem 4.1]. Fukunaga gave a deterministic \(O(n^{rk + O(1)})\) time algorithm for any constant k and constant rank r via a hypertree packing approach [11]. In these cases of \(k \gt 2\), we see the randomized algorithm of Chandrasekaran, Xu, and Yu [6] and our own results do provide improvements over the deterministic algorithms, and the randomized approach is the only one known to work with arbitrarily large hyperedges.

Based on the history above, it seems likely that randomized approaches will eventually lead to even faster algorithms for both min-cut and min-k-cut in hypergraphs. We believe our work is a natural and important step toward this end.

Subsequent to the the conference publication of our work [10], the hypergraph minimum cut and related problems were studied in References [1, 2, 3, 4, 5, 7, 21]. Karger and Williamson [21] provided a streamlined analysis of our algorithm in the case of graph minimum cut. Gupta, Lee, and Li show that the Karger-Stein algorithm is optimal for graph k-cut [15]. Chandrasekaran and Chekuri [4] gave the first deterministic polynomial-time algorithm for hypergraph k-cut, for fixed k. Their approach significantly differs from ours, as it is based on a divide-and-conquer procedure and does not rely on (randomized) contractions. Beideman et al. [1] provided a faster algorithm for hypergraph minimum cut on low-rank simple hypergraphs. Beideman et al. [2, 3] study counting and enumerating optimal hypergraph cuts. Chandrasekaran and Chekuri [5] considered the problem of min-max hypergraph k-cut and gave a polynomial-time algorithm. Finally, Chekuri and Quanrud [7] devised an \(\widetilde{O}(\sqrt {pn(m+n)^{1.5}})\) time algorithm for hypergraph min-cut.

We now give the details for our branching contraction algorithm for min-k-cut in a hypergraph \(H = (V, E)\) of order n. The algorithm for min-cut is the special case for \(k=2\). As we show, a single run of our algorithm has (within constant factors) the same probability of finding a min-k-cut as in the branching algorithm of Karger and Stein [20] for graphs.

We say a hyperedge e is k-spanning if it contains at least \(n - k + 2\) vertices, implying it spans every k-cut. We maintain a collection \(S \subseteq E\) of hyperedges that we believe belong to the min-k-cut based on earlier randomized contractions. Initially, every k-spanning hyperedge is added to S. Then, we sample a random hyperedge e with probability proportional to its weight (or uniformly at random if the hypergraph is unweighted). We contract the hyperedge e to create the hypergraph \(H / e\), and recursively call our algorithm on \(H / e\). With probability \(z_n(e)\), we also branch, meaning we recursively call our algorithm on the same hypergraph H. If we branched, then we return the smaller of the cuts returned for \(H / e\) and our second run on H. Otherwise, we return the cut found for \(H / e\). The algorithm is given in pseudo-code below as the procedure BranchingContract (H, S). It initially takes the empty set as its second parameter.

Consider a single run of BranchingContract on a hypergraph H. We define the computation tree of the run as follows. The computation tree contains as a node the input hypergraph H and each hypergraph created by a contraction (including multiple nodes for identical hypergraphs created by separate branched contractions). It also contains a special root node not associated with any particular hypergraph. The parent of hypergraph \(H^{\prime }\) is the hypergraph from whose contraction \(H^{\prime }\) was created, and the parent of input hypergraph H is the root node. Last, we remark that the non-contracting branch does not create a new node.

A computation tree can be defined similarly for Karger and Stein’s [20] recursive contraction algorithm; here the root node contains two children, one for each of the two independent runs on the input graph. However, while this computation tree is deterministic in its structure and graph orders of its nodes, the structure and hypergraph orders of our computation tree are themselves randomized. In particular, BranchingContract may not yield an isomorphic computation tree to that of the algorithm of Karger and Stein when given a graph as input.

The following lemma bounds the number of hypergraphs of various orders in our computation tree and will prove useful in the analysis of our implementations of BranchingContract. Let \(S(n, n_0)\) denote the maximum expected number of nodes of order \(n_0\) created in a computation tree for some hypergraph H of order n, where the maximum is over all hypergraphs of order n.

We now establish the probability of BranchingContract returning a min-k-cut of hypergraph \(H = (V, E)\). For any integer \(t \ge k\), let

To see that \(\sum _{t=k}^n z_t^* = O(\log n)\), notice that each term \(z_t^* = \Theta (1/t)\), since the numerator is \(O(t^{k-2})\) whereas the denominator is \(O(t^{k-1})\). Now to prove the theorem, we need the following observation. In the proof of Theorem 2.3, we only apply it with \(w=1\), but the general statement given below will be useful in the analysis of our hedgegraph cut algorithm.

We are now ready to prove Theorem 2.3.

Suppose H is an unweighted cycle graph and \(k = 2\), and let C be a minimum cut in H. Assuming BranchingContract breaks ties in C’s favor, it returns C with exactly the probability given in Theorem 2.3.

So far, we have established that the branching randomized contraction algorithm for finding min-cuts and min-k-cuts has an \(\Omega (1 / \log n)\) probability of success when given a hypergraph of order n. In the next two sections, we give efficient implementations of the algorithm for arbitrary and low-rank hypergraphs. It would be natural to boost this probability of success by repeated runs of the algorithm, but this process needs some care, because the running time of our algorithm is also randomized and the length of individual runs can be correlated with the success of the algorithm. This is in contrast with the algorithm of Karger and Stein [20] whose runtime is deterministic. In this case, they may simply run \(\Theta (\log ^2 n)\) independent copies of the branching contraction algorithm and returns the smallest cut found.

Our solution is the following. Suppose we implement our branching contraction algorithm to run in T time in expectation. We can find a minimum cut or k-cut with high probability in worst case \(O(T \log ^2 n)\) time by subtly modifying Karger and Stein’s approach. We say that a batch is a set of \(c \log n\) runs of our algorithm for some sufficiently large constant c. We perform a batch of independent runs by doing the runs sequentially until either all \(c \log n\) runs are complete or \(4cT \log n\) units of time have passed. (For example, if the first run takes longer than \(4cT\log n\) units of time, then no other run in the batch is executed.) The result of the batch is nothing if the \(4cT \log n\) time units have passed or the smallest cut found otherwise. Our overall minimum cut or k-cut algorithm then returns the smallest cut found over \(c^{\prime } \log n\) independent batches for some constant \(c^{\prime }\).

We now prove the following lemma.

Our algorithm needs to perform hyperedge selections and contractions in \(O(n^{r-1})\) time each. Similar to Karger and Stein [20], we rely on some simple data structures to aid in our hyperedge selections instead of naively enumerating all edges and randomly selecting from them. We store a value \(D(v)\) on each vertex v, which is equal to the sum of the weights of all hyperedges of size exactly r containing v. We also maintain \(w(E)\), the total sum of hyperedge weights.

To select a hyperedge for contraction, we enumerate all \(O(n^{r-1})\) hyperedges of size at most \(r-1\). Let \(e_1, \dots , e_t\) be this list of hyperedges. With probabilitywe pick one of \(e_1, \dots , e_t\) with probability proportional to its weight. If we do not pick one of these hyperedges, then we pick a vertex v with probability proportional to \(D(v)\), and then pick one of the \(O(n^{r-1})\) hyperedges of size r containing v with probability proportional to its weight. The running time of this procedure is dominated by the time it takes to enumerate the hyperedges involved in a single probabilistic choice. There are at most \(O(n^{r-1})\) such edges in each case.

We now turn to contractions. Suppose our algorithm needs to contract hyperedge \(e = \left\lbrace v_1, \dots , v_{|e|} \right\rbrace\). We will contract e to one of its vertices, say, \(v_1\in e\). First, we list all \(O(n^{r-1})\) hyperedges that are incident to any vertex of e. Then remove members of \(e - v_1\) from the hyperedges and add \(v_1\) to each hyperedge it does not already appear in. We remove each hyperedge in the list that consists entirely of \(v_1\). Next, we sort the hyperedges of the list as before, and combine identical hyperedges of the list, summing their weights. Finally, we recompute \(D(v_1)\) by summing the weights of all remaining hyperedges in the list. The entire contraction procedure takes \(O(n^{r-1})\) time.

Now, we turn to analyzing our implementation of BranchingContract for hypergraphs of constant rank r. As we will see, the total time spent performing contractions is easily determined using the above discussion and Lemma 2.2’s bound on the number of hypergraphs of different orders in the computation tree. The only other operation we have yet to analyze is the time spent making copies of hypergraphs while branching. In particular, if there is a hypergraph \(H^{\prime }\) in the computation tree with t children, then we need to create \(t-1\) copies of \(H^{\prime }\).

By applying our analysis for boosting the probability of success (Lemma 2.4), we obtain our main results for constant rank hypergraphs.