@inproceedings{db0e2b4cce30403aab554e26481986c0,

title = "Computing minimum cuts in hypergraphs",

abstract = "We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph H = (V;E) with n = V , m = E and p = P e2E 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 + n2 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 H0 with sum of degrees O(kn) that preserves all edge-connectivities up to k (a k-sparsier). 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. 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( 1 (p log n + n log2 n)) 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 + n2 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.",

author = "Chandra Chekuri and Chao Xu",

note = "Publisher Copyright: Copyright {\textcopyright} by SIAM.; 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 ; Conference date: 16-01-2017 Through 19-01-2017",

year = "2017",

doi = "10.1137/1.9781611974782.70",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1085--1100",

editor = "Klein, {Philip N.}",

booktitle = "28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017",

address = "United States",

}