TY - GEN

T1 - Computing minimum cuts in hypergraphs

AU - Chekuri, Chandra

AU - Xu, Chao

N1 - Publisher Copyright:
Copyright © by SIAM.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85016167578&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85016167578&partnerID=8YFLogxK

U2 - 10.1137/1.9781611974782.70

DO - 10.1137/1.9781611974782.70

M3 - Conference contribution

AN - SCOPUS:85016167578

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1085

EP - 1100

BT - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

A2 - Klein, Philip N.

PB - Association for Computing Machinery

T2 - 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017

Y2 - 16 January 2017 through 19 January 2017

ER -