Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2009-016 (August 05, 2009)

Computing Minimum Multiway Cuts in Hypergraphs from Hypertree Packings
by Takuro Fukunaga

pdf File

Hypergraph multiway cut problem is a problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into a specified number of connected components. We present an algorithm for this problem which runs in strongly polynomial-time if both the specified number of connected components and the maximum size of hyperedges in the hypergraph are constants. Our algorithm extends the algorithm due to Thorup (2008) for computing minimum multiway cuts of graphs from greedy packings of spanning trees.