Counting and enumerating optimum cut sets for hypergraph $k$-partitioning problems for fixed $k$¹¹1University of Illinois, Urbana-Champaign. Email: {calvinb2, karthe, weihang3}@illinois.edu. Supported in part by NSF grants CCF-1814613 and CCF-1907937.

In contrast to graphs, whose representation size is the number of edges, the representation size of a hypergraph $G=(V,E)$ is $p:=\sum_{e\in E}|e|$. Throughout, our algorithmic discussion will focus on the case of fixed $k$ (e.g., $k=2,3,4,\ldots$).

There are no prior results regarding Enum-MinMax-Hypergraph-$k$-Partition in the literature. We recall the status of Minmax-Hypergraph-$k$-Partition. As mentioned earlier, Minmax-Hypergraph-$k$-Partition was discussed as early as 1973 by Lawler [43] with its complexity status being open until recently. We note that the objective here could be viewed as aiming to find a fair $k$-partition, i.e., a $k$-partition where no part pays too much in cut value. Motivated by this connection to fairness, Chandrasekaran and Chekuri (2021) [12] studied the more general problem of Minmax-SymSubmod-$k$-Partition. They gave the first (deterministic) polynomial-time algorithm to solve Minmax-SymSubmod-$k$-Partition and as a consequence, obtained the first polynomial-time algorithm to solve Minmax-Hypergraph-$k$-Partition. Their algorithm does not show any bound on the number of minmax-$k$-cut-sets since it solves the more general problem of Minmax-SymSubmod-$k$-Partition for which the number of optimum $k$-partitions can indeed be exponential (recall the spanning-hyperedge-example). Focusing on hypergraphs raises the question of whether all $k$-cut-sets corresponding to optimum solutions can be enumerated efficiently for every fixed $k$. We answer this question affirmatively by giving the first polynomial-time algorithm for Enum-MinMax-Hypergraph-$k$-Partition.

We emphasize that our result shows the first polynomial bound on the number of minmax-$k$-cut-sets in hypergraphs for every fixed $k$ (in addition to a polynomial-time algorithm to enumerate all of them for every fixed $k$). Our upper bound of $n^{O(k^{2})}$ on the number of minmax-$k$-cut-sets is tight—there exist $n$-vertex connected graphs for which the number of minmax-$k$-cut-sets is $n^{\Theta(k^{2})}$ (see Section 6).

Next, we briefly recall the status of Hypergraph-$k$-Cut and Enum-Hypergraph-$k$-Cut. Hypergraph-$k$-Cut was shown to be solvable in randomized polynomial time only recently [14, 23]; the randomized algorithms also showed that the number of min-$k$-cut-sets is $O(n^{2k-2})$ and they can all be enumerated in randomized polynomial time. A subsequent deterministic algorithm was designed to solve Hypergraph-$k$-Cut in time $n^{O(k)}p$ by Chandrasekaran and Chekuri [11]. Chandrasekaran and Chekuri’s techniques were extended to design the first deterministic polynomial-time algorithm to solve Enum-Hypergraph-$k$-Cut in [7]. The algorithm for Enum-Hypergraph-$k$-Cut given in [7] runs in time $n^{O(k^{2})}p$. We note that this run-time has a quadratic dependence on $k$ in the exponent of $n$ although the number of min-$k$-cut-sets has only linear dependence on $k$ in the exponent of $n$ (since it is $O(n^{2k-2})$). So, an open question that remained from [7] is whether one can obtain an $n^{O(k)}p$-time deterministic algorithm for Enum-Hypergraph-$k$-Cut. We resolve this question affirmatively.

Our algorithms for both Enum-MinMax-Hypergraph-$k$-Partition and Enum-Hypergraph-$k$-Cut are based on a structural theorem that allows for efficient recovery of optimum $k$-cut-sets via minimum $(s,t)$-terminal cuts (see Theorem 1.4). Our structural theorem builds on structural theorems that have appeared in previous works on Minmax-Hypergraph-$k$-Partition and Hypergraph-$k$-Cut [11, 12, 7]. Our structural theorem may appear to be natural/incremental in comparison to ones that appeared in previous works, but formalizing the theorem and proving it is a significant part of our contribution. Moreover, our single structural theorem is strong enough to enable efficient algorithms for both Enum-Hypergraph-$k$-Cut as well as Enum-MinMax-Hypergraph-$k$-Partition in contrast to previously known structural theorems. In this sense, our structural theorem can be viewed as a strong and unifying generalization of structural theorems that have appeared in previous works. We believe that our structural theorem will be of independent interest in the theory of cuts and partitioning in hypergraphs (as well as graphs).

We focus on the unit-cost variant of Enum-Hypergraph-$k$-Cut and Enum-MinMax-Hypergraph-$k$-Partition in the rest of this work for the sake of notational simplicity—i.e., the cost of every hyperedge is $1$. Throughout, we will allow multigraphs and hence, this is without loss of generality. Our algorithms extend in a straightforward manner to arbitrary hyperedge costs. They rely only on minimum $(s,t)$-terminal cut computations and hence, they are strongly polynomial-time algorithms.

Our technique to enumerate all minmax-$k$-cut-sets and all min-$k$-cut-sets will build on the approaches of Chandrasekaran and Chekuri for Hypergraph-$k$-Cut and Minmax-SymSubmod-$k$-Partition [11, 12, 7]. We need the following structural theorem that was shown in [7].

We encourage the reader to compare and contrast Theorems 1.3 and 1.4. The former helps to recover cuts whose cut value is strictly smaller than $OPT_{k\text{-cut}}$ while the latter helps to recover cut-sets whose size is equal to $OPT_{k\text{-cut}}$. So, the latter theorem is weaker since it only recovers cut-sets, but we emphasize that this is the best possible that one can hope to do (as seen from the spanning-hyperedge-example). However, proving the latter theorem requires us to work with cut-sets (as opposed to cuts) which is a technical barrier to overcome. Indeed, our proof of Theorem 1.4 deviates significantly from the proof of Theorem 1.3 since we have to work with cut-sets. Our proof also deviates from the structural result in [7] that was mentioned in the paragraph above Theorem 1.4 since our result is stronger than their result—our result helps to recover the cut-set $\delta(U)$ of an arbitrary cut $(U,\overline{U})$ whose cut value is $d(U)=OPT_{k\text{-cut}}$ while their result helps only to recover the cut-set $\delta(V_{i})$ of a part $V_{i}$ of an optimum $k$-partition $(V_{1},\ldots,V_{k})$ for Hypergraph-$k$-Cut whose cut value is $d(V_{i})=OPT_{k\text{-cut}}$; moreover, their proof technique crucially relies on a containment property with respect to the part $V_{i}$, whereas under the hypothesis of our structural theorem, the containment property fails with respect to the set $U$ and consequently, our proof technique differs from theirs.

Theorems 1.3 and 1.4 lead to a deterministic $n^{O(k)}$-time algorithm to enumerate all min-$k$-cut-sets via a divide-and-conquer approach. We describe this algorithm now: For each pair $(S,T)$ of disjoint subsets of vertices $S$ and $T$ with $|S|$, $|T|\leq 2k-1$, compute the source minimal minimum $(S,T)$-terminal cut $(A,\overline{A})$; (i) if $G-\delta(A)$ has at least $k$ connected components, then add $\delta(A)$ to the candidate family $\mathcal{F}$; (ii) otherwise, add the set $A$ to a collection $\mathcal{C}$. We note that the sizes of the family $\mathcal{F}$ and the collection $\mathcal{C}$ are $O(n^{4k-2})$. Next, for each subset $A$ in the collection $\mathcal{C}$, recursively enumerate all min-$k/2$-cut-sets in the subhypergraphs induced by $A$ and $\overline{A}$ respectively⁶⁶6Subhypergraph $G[A]$ has vertex set $A$ and contains all hyperedges of $G$ which are entirely contained within $A$.—denoted $G[A]$ and $G[\overline{A}]$ respectively—and add $\delta(A)\cup F_{1}\cup F_{2}$ to the family $\mathcal{F}$ for each $F_{1}$ and $F_{2}$ being min-$k/2$-cut-set in $G[A]$ and $G[\overline{A}]$ respectively. Finally, return the subfamily of $k$-cut-sets from the family $\mathcal{F}$ that are of smallest size.

We sketch the correctness analysis of the above approach: let $F=\delta(V_{1},\ldots,V_{k})$ be a min-$k$-cut-set with $(V_{1},\ldots,V_{k})$ being an optimum $k$-partition for Hypergraph-$k$-Cut. We will show that the family $\mathcal{F}$ contains $F$. Let $U:=\cup_{i=1}^{k/2}V_{i}$. We note that $\delta(U)\subseteq F$. We have two possibilities: (1) Say $d(U)=|F|$. Then, $d(U)=OPT_{k\text{-cut}}$. Consequently, by Theorem 1.4, the min-$k$-cut-set $F$ will be added to the family $\mathcal{F}$ by step (i). (2) Say $d(U)<|F|$. Then, by Theorem 1.3, the set $U=\cup_{i=1}^{k/2}V_{i}$ will be added to the collection $\mathcal{C}$ by step (ii); moreover, $F_{1}:=F\cap E(G[U])$ and $F_{2}:=F\cap E(G[\overline{U}])$ are min-$k/2$-cut-sets in $G[U]$ and $G[\overline{U}]$ respectively and they would have been enumerated by recursion, and hence, the set $\delta(U)\cup F_{1}\cup F_{2}=F$ will be added to the family $\mathcal{F}$. The size of the family $\mathcal{F}$ can be shown to be $n^{O(k\log{k})}$ and the run-time is $n^{O(k\log{k})}p$ (see Theorem 4.1). Using the known fact that the number of min-$k$-cut-sets in a $n$-vertex hypergraph is $O(n^{2k-2})$, we can improve the run-time analysis of this approach to $n^{O(k)}p$ (see Lemma 4.1).

Why is this issue significant while solving Enum-MinMax-Hypergraph-$k$-Partition? We recall that in our approach for Enum-Hypergraph-$k$-Cut, the algorithm computed a polynomial-sized family $\mathcal{F}$ containing all min-$k$-cut-sets and returned the ones with smallest size—the smallest size ones will exactly be min-$k$-cut-sets. It is unclear if a similar approach could work for enumerating minmax-$k$-cut-sets: suppose we do have an algorithm to enumerate a polynomial-sized family $\mathcal{F}$ containing all minmax-$k$-cut-sets; now, in order to return all minmax-$k$-cut-sets (which is a subfamily of $\mathcal{F}$), note that we need to identify them among the ones in the family $\mathcal{F}$—i.e., we need to verify if a given subset $F\in\mathcal{F}$ of hyperedges is a minmax-$k$-cut-set; this verification problem is closely related to the question mentioned in the previous paragraph. We do not know how to address this verification problem directly. So, our algorithmic approach for Enum-MinMax-Hypergraph-$k$-Partition has to overcome this technical issue.

Our ingredient to overcome this technical issue is to enumerate representatives for minmax-$k$-cut-sets. For a $k$-partition $(V_{1},\ldots,V_{k})$ and disjoint subsets $U_{1},\ldots,U_{k}\subseteq V$, we will call the $k$-tuple $(U_{1},\ldots,U_{k})$ to be a $k$-cut-set representative of $(V_{1},\ldots,V_{k})$ if $U_{i}\subseteq V_{i}$ and $\delta(U_{i})=\delta(V_{i})$ for all $i\in[k]$. We note that a fixed $k$-partition $(V_{1},\ldots,V_{k})$ could have several $k$-cut-set representatives and a fixed $k$-tuple $(U_{1},\ldots,U_{k})$ could be the $k$-cut-set representative of several $k$-partitions. Yet, it is possible to efficiently verify if a given $k$-tuple $(U_{1},\ldots,U_{k})$ is a $k$-cut-set representative (Theorem 5.1). Moreover, knowing a $k$-cut-set representative $(U_{1},\ldots,U_{k})$ of a $k$-partition $(V_{1},V_{2},\ldots,V_{k})$ allows one to recover the $k$-cut-set $F:=\delta(V_{1},\ldots,V_{k})$ since $F=\cup_{i=1}^{k}\delta(U_{i})$. Thus, in order to enumerate all minmax-$k$-cut-sets, it suffices to enumerate $k$-cut-set representatives of all optimum $k$-partitions for Minmax-Hypergraph-$k$-Partition. At this point, the astute reader may wonder if there exists a polynomial-sized family of $k$-cut-set representatives of all optimum $k$-partitions for Minmax-Hypergraph-$k$-Partition given that the number of optimum $k$-partitions for Minmax-Hypergraph-$k$-Partition could be exponential. For example, is there a polynomial-sized family of $k$-cut-set representatives of all optimum $k$-partitions for Minmax-Hypergraph-$k$-Partition in the spanning-hyperedge-example? Indeed, in the spanning-hyperedge-example, even though the number of optimum $k$-partitions for Minmax-Hypergraph-$k$-Partition is exponential, there exists a $(k!\binom{n}{k})$-sized family of $k$-cut-set representatives of all optimum $k$-partitions: consider the family $\{(\{v_{1}\},\ldots,\{v_{k}\}):v_{1},\ldots,v_{k}\in V,v_{i}\neq v_{j}\ \forall\ \text{distinct }i,j\in[k]\}$.

It turns out that Theorems 1.3 and 1.4 are strong enough to enable efficient enumeration of $k$-cut-set representatives of all optimum $k$-partitions for Minmax-Hypergraph-$k$-Partition. We describe the algorithm to achieve this: For each pair $(S,T)$ of disjoint subsets of vertices with $|S|$, $|T|\leq 2k-1$, compute the source minimal minimum $(S,T)$-terminal cut $(U,\overline{U})$ and add $U$ to a candidate collection $\mathcal{C}$. We note that the size of the collection $\mathcal{C}$ is $O(n^{4k-2})$. Next, for each $k$-tuple $(U_{1},\ldots,U_{k})\in\mathcal{C}^{k}$, verify if $(U_{1},\ldots,U_{k})$ is a $k$-cut-set representative (using Theorem 5.1) and if so, then add the $k$-tuple to the candidate family $\mathcal{D}$. Finally, return $\arg\min\{\max_{i=1}^{k}d(U_{i}):(U_{1},\ldots,U_{k})\in\mathcal{D}\}$, i.e., prune and return the subfamily of $k$-cut-set representatives $(U_{1},\ldots,U_{k})$ from the family $\mathcal{D}$ that have minimum $\max_{i=1}^{k}d(U_{i})$.

We note that the size of the family $\mathcal{D}$ is $n^{O(k^{2})}$ and consequently, the run-time is $n^{O(k^{2})}p$. We sketch the correctness analysis of the above approach: let $(V_{1},\ldots,V_{k})$ be an optimum $k$-partition for Minmax-Hypergraph-$k$-Partition. We will show that the family $\mathcal{D}$ contains a $k$-cut-set representative of $(V_{1},\ldots,V_{k})$. By noting that $OPT_{\text{minmax-}k\text{-partition}}\leq OPT_{k\text{-cut}}$ and by Theorems 1.3 and 1.4, for every $i\in[k]$, we have a set $U_{i}$ in the collection $\mathcal{C}$ with $U_{i}\subseteq V_{i}$ and $\delta(U_{i})=\delta(V_{i})$. Hence, the $k$-tuple $(U_{1},\ldots,U_{k})\in\mathcal{C}^{k}$ is a $k$-cut-set representative and it will be added to the family $\mathcal{D}$. The final pruning step will not remove $(U_{1},\ldots,U_{k})$ from the family $\mathcal{D}$ and hence, it will be in the subfamily returned by the algorithm.

We briefly discuss the status of the enumeration problems for $k=2$ followed by the status for $k\geq 2$ in graphs and hypergraphs.

Graph-$k$-Cut for fixed $k$ was shown to be polynomial-time solvable by Goldschmidt and Hochbaum [26]. Subsequently, Karger and Stein [38] gave a randomized polynomial-time algorithm whose analysis also showed that the number of optimum $k$-partitions in a connected graph is $O(n^{2k-2})$ and they can all be enumerated in polynomial time for every fixed $k$ (also see [34, 58, 57, 17]). The number of optimum $k$-partitions has recently been improved to $O(n^{k})$ for fixed $k$ thereby leading to a faster algorithm for Graph-$k$-Cut for fixed $k$ [31, 32, 28].

Hypergraph-$k$-Cut for fixed $k$ was recently shown to be polynomial-time solvable via a randomized algorithm [14, 23]. The analysis of the randomized algorithm also showed that the number of min-$k$-cut-sets is $O(n^{2k-2})$ and they can all be enumerated in randomized polynomial time. A deterministic polynomial-time algorithm was given by Chandrasekaran and Chekuri [11]. Subsequently, a deterministic polynomial-time algorithm for Enum-Hypergraph-$k$-Cut for fixed $k$ was given by Beideman, Chandrasekaran, and Wang [7].

Minmax-Graph-$k$-Partition for fixed $k$ is polynomial-time solvable via the following observation (see [13, 12]): in connected graphs, an optimum $k$-partition for Minmax-Graph-$k$-Partition is a $k$-approximate solution to Graph-$k$-Cut. The randomized algorithm of Karger and Stein implies that the number of $k$-approximate solutions to Graph-$k$-Cut is $n^{O(k^{2})}$ and they can all be enumerated in polynomial time [38, 17, 32, 28]. These two facts together imply that Minmax-Graph-$k$-Partition can be solved in time $n^{O(k^{2})}$ and moreover, the number of optimum $k$-partitions for Minmax-Graph-$k$-Partition in a connected graph is $n^{O(k^{2})}$ and they can all be enumerated in polynomial time for constant $k$.

For a detailed discussion on other hypergraph $k$-partitioning problems that are special cases of Minsum-Submod-$k$-Partition, we refer the reader to [61, 60, 50].

Let $G=(V,E)$ be a hypergraph. Throughout, we will follow the notation mentioned in the second paragraph of Section 1.2. For disjoint $A,B\subseteq V$, we define $E(A,B):=\{e\in E:e\subseteq A\cup B,e\cap A\neq\emptyset,e\cap B\neq\emptyset\}$, and $E[A]:=\{e\in E:e\subseteq A\}$. We will repeatedly rely on the fact that the hypergraph cut function $d:2^{V}\rightarrow\mathbb{R}_{+}$ is symmetric and submodular. We recall that a set function $f:2^{V}\rightarrow\mathbb{R}$ is symmetric if $f(U)=f(\overline{U})$ for all subsets $U\subseteq V$ and is submodular if $f(A)+f(B)\geq f(A\cap B)+f(A\cup B)$ for all subsets $A,B\subseteq V$.

We will need the following partition uncrossing theorem that was proved in previous works on Hypergraph-$k$-Cut and Enum-Hypergraph-$k$-Cut (see Figure 1 for an illustration of the sets that appear in the statement of Theorem 1.5):