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.