Abstract
We consider the problem of enumerating optimal solutions for two hypergraph kpartitioning problems  namely, HypergraphkCut and MinmaxHypergraphkPartition. The input in hypergraph kpartitioning 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 nonempty parts (V₁, V₂, …, V_k)  known as a kpartition  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 MinmaxHypergraphkPartition. A subset of hyperedges is a minmaxkcutset if it is the subset of hyperedges crossing an optimum kpartition for MinmaxHypergraphkPartition.
2) If the objective of interest is the total cost of hyperedges crossing the kpartition, then the problem is known as HypergraphkCut. A subset of hyperedges is a minkcutset if it is the subset of hyperedges crossing an optimum kpartition for HypergraphkCut.
We give the first polynomial bound on the number of minmaxkcutsets and a polynomialtime algorithm to enumerate all of them in hypergraphs for every fixed k. Our technique is strong enough to also enable an n^{O(k)}ptime deterministic algorithm to enumerate all minkcutsets in hypergraphs, thus improving on the previously known n^{O(k²)}ptime 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 HypergraphkCut and MinmaxHypergraphkPartition. We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).
BibTeX  Entry
@InProceedings{beideman_et_al:LIPIcs.ICALP.2022.16,
author = {Beideman, Calvin and Chandrasekaran, Karthekeyan and Wang, Weihang},
title = {{Counting and Enumerating Optimum Cut Sets for Hypergraph kPartitioning Problems for Fixed k}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {16:116:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16357},
URN = {urn:nbn:de:0030drops163578},
doi = {10.4230/LIPIcs.ICALP.2022.16},
annote = {Keywords: hypergraphs, kpartitioning, counting, enumeration}
}
Keywords: 

hypergraphs, kpartitioning, counting, enumeration 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 