Computing minimum cuts in hypergraphs

We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph $H=(V,E)$ with $n=\mathrm{\mid }V\mathrm{\mid }$, $m=\mathrm{\mid }E\mathrm{\mid }$ and $p = \sum_{e \in E} |e|$thebestknownalgorithmtocomputeaglobalminimumcutin$H$ runs in time $O(np)$ for the uncapacitated case and in $O(np+n^2\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^{\mathrm{\prime }}$ 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

• \lambda n^2)$timealgorithmforcomputingaglobalminimumcutof$H$where$\lambda$ 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(\frac{1}{ϵ}(p\log n+n{\log }^{2}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+n^2\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.