# Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k

Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang

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

## Abstract

We consider the problem of enumerating optimal solutions for two hypergraph k-partitioning problems - namely, Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. The input in hypergraph k-partitioning problems is a hypergraph G = (V, E) with positive hyperedge costs along with a fixed positive integer k. The goal is to find a partition of V into k non-empty parts (V1, V2,..., Vk) - known as a k-partition - so as to minimize an objective of interest. 1. If the objective of interest is the maximum cut value of the parts, then the problem is known as Minmax-Hypergraph-k-Partition. A subset of hyperedges is a minmax-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Minmax-Hypergraph-k-Partition. 2. If the objective of interest is the total cost of hyperedges crossing the k-partition, then the problem is known as Hypergraph-k-Cut. A subset of hyperedges is a min-k-cut-set if it is the subset of hyperedges crossing an optimum k-partition for Hypergraph-k-Cut. We give the first polynomial bound on the number of minmax-k-cut-sets and a polynomial-time algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an nO(k)p-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known nO(k2)p-time deterministic algorithm, where n is the number of vertices and p is the size of the hypergraph. The correctness analysis of our enumeration approach relies on a structural result that is a strong and unifying generalization of known structural results for Hypergraph-k-Cut and Minmax-Hypergraph-k-Partition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).

Original language English (US) 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing 9783959772358 https://doi.org/10.4230/LIPIcs.ICALP.2022.16 Published - Jul 1 2022 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, FranceDuration: Jul 4 2022 → Jul 8 2022

### Publication series

Name Leibniz International Proceedings in Informatics, LIPIcs 229 1868-8969

### Conference

Conference 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 France Paris 7/4/22 → 7/8/22

## Keywords

• counting
• enumeration
• hypergraphs
• k-partitioning

• Software

## Fingerprint

Dive into the research topics of 'Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k'. Together they form a unique fingerprint.