## 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 language | English (US) |
---|---|

Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 |

Publisher | Association for Computing Machinery |

Pages | 2208-2228 |

Number of pages | 21 |

ISBN (Electronic) | 9781611977073 |

State | Published - 2022 |

Event | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 - Alexander, United States Duration: Jan 9 2022 → Jan 12 2022 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2022-January |

### Conference

Conference | 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022 |
---|---|

Country/Territory | United States |

City | Alexander |

Period | 1/9/22 → 1/12/22 |

## ASJC Scopus subject areas

- Software
- General Mathematics