Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k

We consider the problem of deterministically enumerating all minimum k-cut-sets in a given hypergraph for fixed constant k. The input here is a hypergraph G=(V,E) with non-negative hyperedge costs. A subset F⊆E of hyperedges is a k-cut-set if the number of connected components in G-F is at least k and it is a minimum k-cut-set if it has the least cost among all k-cut-sets. For fixed k, we call the problem of finding a minimum k-cut-set as Hypergraph-k-Cut and the problem of enumerating all minimum k-cut-sets as Enum-Hypergraph-k-Cut. The special cases of Hypergraph-k-Cut and Enum-Hypergraph-k-Cut restricted to graph inputs are well-known to be solvable in (randomized as well as deterministic) polynomial time (Goldschmidt and Hochbaum in Math Oper Res 19(1):24–37, 1994; Karger and Stein in J ACM 43(4):601–640, 1996; Kamidoi et al. in SIAM J Comput 36(5):1329–1341, 2007; Thorup, in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC, 2008). In contrast, it is only recently that polynomial-time algorithms for Hypergraph-k-Cut were developed (Chandrasekaran et al. in Math Program 186:85–113, 2019; Fox et al., in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA, 2019; Chandrasekaran and Chekuri in Math Oper Res 47:3380–3399, 2022). The randomized polynomial-time algorithm for Hypergraph-k-Cut that was designed in 2018 (Chandrasekaran et al. 2019) showed that the number of minimum k-cut-sets in a hypergraph is O(n^2k-2), where n is the number of vertices in the input hypergraph, and that they can all be enumerated in randomized polynomial time, thus resolving Enum-Hypergraph-k-Cut in randomized polynomial time. A deterministic polynomial-time algorithm for Hypergraph-k-Cut was subsequently designed in 2020 (Chandrasekaran and Chekuri 2022), but it is not guaranteed to enumerate all minimum k-cut-sets. In this work, we give the first deterministic polynomial-time algorithm to solve Enum-Hypergraph-k-Cut (this is non-trivial even for k=2). Our algorithm is based on new structural results that allow for efficient recovery of all minimum k-cut-sets by solving minimum (S, T)-terminal cuts. Our techniques give new structural insights even for minimum cut-sets (i.e., minimum 2-cut-sets) in hypergraphs—we give a new proof showing that the number of minimum cut-sets in a n-vertex hypergraph is at most n2 and they can all be enumerated in deterministic polynomial time for a given hypergraph.