Minimum cut and minimum k-cut in hypergraphs via branching contractions

Conference Paper

On hypergraphs with m hyperedges and n vertices, where p denotes the total size of the hyperedges, we provide the following results: • We give an algorithm that runs in Oe mn2k−2 time for finding a minimum k-cut in hypergraphs of arbitrary rank. This algorithm betters the previous best running time for the minimum k-cut problem, for k > 2. • We give an algorithm that runs in Oe nmax{r2k−2} time for finding a minimum k-cut in hypergraphs of constant rank r. This algorithm betters the previous best running times for both the minimum cut and minimum k-cut problems for dense hypergraphs. Both of our algorithms are Monte Carlo, i.e., they return a minimum k-cut (or minimum cut) with high probability. These algorithms are obtained as instantiations of a generic branching randomized contraction technique on hypergraphs, which extends the celebrated work of Karger and Stein on recursive contractions in graphs. Our techniques and results also extend to the problems of minimum hedge-cut and minimum hedge-k-cut on hedgegraphs, which generalize hypergraphs.

Full Text

Duke Authors

Cited Authors

  • Fox, K; Panigrahi, D; Zhang, F

Published Date

  • January 1, 2019

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 881 - 896

Digital Object Identifier (DOI)

  • 10.1137/1.9781611975482.54

Citation Source

  • Scopus