2016/07/29 by Chandra Chekuri, Chao Xu, Chekuri, Chandra +1 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1607.08682
openalex publication_date 2016/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 best known algorithm to compute a global minimum cut in H runs in time O(np) for the uncapacitated case and in O(np + n2 log n) time for the capacitated case. We show the following new results. 1. 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 + λn2) time algorithm for computing a global minimum cut of H where λ is the minimum cut value. 2. We generalize Matula's argument for graphs to hypergraphs and obtain a (2+ε)-approximation to the global minimum cut in a capacitated hypergraph in O(\frac1ε (p log n + n log2 n)) time. 3. We show that a hypercactus representation of all the global minimum cuts of a capacitated hypergraph can be computed in O(np + n2 log n) time and O(p) space. We utilize vertex ordering based ideas to obtain our results. Unlike graphs we observe that there are several different orderings for hypergraphs which yield different insights.