Computing minimum cuts in hypergraphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages1085-1100
Number of pages16
ISBN (Electronic)9781611974782
DOIs
StatePublished - 2017
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Conference

Conference28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Computing minimum cuts in hypergraphs'. Together they form a unique fingerprint.

Cite this