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

• 成果类型: Article
• 署名作者: Beideman, Calvin; Chandrasekaran, Karthekeyan; Wang, Weihang
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-023-02013-8
• 发表日期: 2024
• 页码: 329-367
• 关键词: phase retrieval; stochastic-approximation; Composite optimization; convex; minimization; RECOVERY

摘要

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 subset of 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(n2k-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 ((n)(2)) and they can all be enumerated in deterministic polynomial time for a given hypergraph.