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

Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of deterministically enumerating all minimum k-cut-sets in a given hypergraph for any fixed 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 [17,25,28,39]. In contrast, it is only recently that polynomial-time algorithms for Hypergraph-k-Cut were developed [2,3,12]. The randomized polynomial-time algorithm for Hypergraph-k-Cut that was designed in 2018 [3] showed that the number of minimum k-cut-sets in a hypergraph is O(n2k2), 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 [2], 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 enumerating all minimum cut-sets (i.e., minimum 2-cut-sets) in a given hypergraph.

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2022
PublisherAssociation for Computing Machinery
Pages2208-2228
Number of pages21
ISBN (Electronic)9781611977073
StatePublished - 2022
Event33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States
Duration: Jan 9 2022Jan 12 2022

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2022-January

Conference

Conference33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Country/TerritoryUnited States
CityAlexander
Period1/9/221/12/22

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Deterministic enumeration of all minimum k-cut-sets in hypergraphs for fixed k'. Together they form a unique fingerprint.

Cite this