The hypergraph k-cut problem is the problem of finding a minimum capacity set of hyper-edges 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.
展开▼
