## 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 (V_{1}, V_{2},..., V_{k}) - 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 n^{O(k)}p-time deterministic algorithm to enumerate all min-k-cut-sets in hypergraphs, thus improving on the previously known n^{O(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) |
---|---|

Title of host publication | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 |

Editors | Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772358 |

DOIs | |

State | Published - Jul 1 2022 |

Event | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, France Duration: Jul 4 2022 → Jul 8 2022 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 229 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 |
---|---|

Country/Territory | France |

City | Paris |

Period | 7/4/22 → 7/8/22 |

## Keywords

- counting
- enumeration
- hypergraphs
- k-partitioning

## ASJC Scopus subject areas

- Software