Computing minimum cuts in hypergraphs

We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph H = ( V, E ) with n = │V│, m = |E| and p = Σ e∊E l e l the fastest known algorithm to compute a global minimum cut in H runs in O ( np ) time for the uncapacitated case, and in O ( np + n 2 log n ) time for the capacitated case. We show the following new results. Given an uncapacitated hypergraph H and an integer k we describe an algorithm that runs in O (p) time to find a subhypergraph H ’ with sum of degrees O ( kn ) that preserves all edge-connectivities up to k (a k -sparsifier). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an O ( p + Λ n 2 ) time algorithm for computing a global minimum cut of H where λ is the minimum cut value. We generalize Matula's argument for graphs to hy- pergraphs and obtain a (2 + ∊ )-approximation to the global minimum cut in a capacitated hypergraph in time, and in in O ( p / ∊ ) time for uncapacitated hypergraphs. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O ( np + n 2 log n ) time and O (p) space. Our results build upon properties of vertex orderings that were inspired by the maximum adjacency ordering for graphs due to Nagamochi and Ibaraki. Unlike graphs we observe that there are several different orderings for hypergraphs which yield different insights.

Authors

• Chandra Chekuri
• Chao Xu 0002

Keywords

No keywords are indexed for this paper.