Given a hypergraph H=(V,E), we consider two problems--Hypergraph Min-cut, where the goal is to find a 2-partition of V that minimizes the number of hyperedges crossing the 2-partition, and Hypergraph k-cut, where the goal is to find a k-partition of V that minimizes the number of hyperedges crossing the k-partition. Our goal is to enumerate all optimum solutions in polynomial time. For each problem, the number of optimum solutions could be exponential, but the number of hyperedge sets corresponding to optimum solutions (denoted min-cut-sets and min-k-cut-sets, respectively) is polynomial (k is a fixed constant for Hypergraph k-cut). Our algorithms enumerate min-cut-sets and min-k-cut-sets (instead of 2-partitions and k-partitions, respectively), relying on structural results that relate optimum min-cut-sets and min-k-cut-sets to min (S,T)-cut for small vertex sets S and T.
This is joint work with Calvin Beideman and Karthekeyan Chandrasekaran.
