Computing minimum multiway cuts in hypergraphs

The hypergraph k-cut problem is the problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into at least k connected components. We present an algorithm for this problem, that runs in strongly polynomial time if both k and the maximum size of the hyperedges are constants. Our algorithm extends the algorithm proposed by Thorup (2008) for computing minimum k-cuts of graphs from greedy packings of spanning trees.