Minimum cuts and sparsification 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 |e| 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 ² log n) time for the capacitated case. We show the following new results. Given an uncapacitated hypergraph H and an integer κ we describe an algorithm that runs in O(p) time to find a (trimmed) subhypergraph H ¹ with sum of degrees O(κn) that preserves all edge-connectivities up to κ (a κ-sparse certificate). This generalizes the corresponding result of Nagamochi and Ibaraki from graphs to hypergraphs. Using this sparsification we obtain an O(p + λn ² ) time algorithm for computing a global minimum cut of H where λ is the minimum cut value. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O(np + n ² log n) time and O(p) space matching the asymptotic time to find a single minimum cut. We obtain a (2 + ϵ)-approximation to the global minimum cut of a capacitated hypergraph in O(1/ϵ (p log n + n log ² n)) time and for uncapacitated hypergraphs in O(p/ϵ) time. We achieve this by generalizing Matula's algorithm for graphs to hypergraphs. We describe an algorithm to compute approximate strengths of all the edges of a hypergraph in O(p log ² n log p) time. This gives a near linear time algorithm for finding a (1 + ϵ)-cut sparsifier based on the work of Kogan and Krauthgamer. As a byproduct we obtain faster algorithms for various cut and flow problems in hypergraphs of small rank. 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 orderings for hypergraphs, and these yield different insights.