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

We consider the problem of enumerating optimal solutions for two hypergraph k -partitioning problems, namely, H ypergraph - k -C ut and M inmax -H ypergraph - k -P artition . 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 nonempty 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 M inmax -H ypergraph - k -P artition . A subset of hyperedges is a minmax - k - cut - set if it is the subset of hyperedges crossing an optimum k -partition for M inmax -H ypergraph - k -P artition . (2) If the objective of interest is the total cost of hyperedges crossing the k -partition, then the problem is known as H ypergraph - k -C ut . A subset of hyperedges is a min - k - cut - set if it is the subset of hyperedges crossing an optimum k -partition for H ypergraph - k -C ut . We give the first polynomial bound on the number of minmax - k - cut - set s 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 - set s in hypergraphs, thus improving on the previously known n O ( k 2 ) p -time deterministic algorithm, in which 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 H ypergraph - k -C ut and M inmax -H ypergraph - k -P artition . We believe that our structural result is likely to be of independent interest in the theory of hypergraphs (and graphs).