Computing minimum cuts in hypergraphs

DOI10.1137/1.9781611974782.70MaRDI QIDQ4575811zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Chao Xu

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1607.08682

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Connectivity (05C40) Hypergraphs (05C65)

Abstract: We study algorithmic and structural aspects of connectivity in hypergraphs. Given a hypergraph $H=(V,E)$ with $n=|V|$, $m=|E|$ and $p=su{m}_{einE}|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+n^{2}logn)$ 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^{\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)$ time algorithm for computing a global minimum cut of $H$ where $lambda$ is the minimum cut value. 2. We generalize Matula's argument for graphs to hypergraphs and obtain a $(2+epsilon)$-approximation to the global minimum cut in a capacitated hypergraph in $O(frac1epsilon(plogn+nlo{g}^{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}logn)$ 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.

Recommendations

• Minimum cuts and sparsification in hypergraphs
• Computing minimum multiway cuts in hypergraphs
• Minimum cut and minimum \(k\)-cut in hypergraphs via branching contractions
• Computing minimum multiway cuts in hypergraphs from hypertree packings
• Faster connectivity in low-rank hypergraphs via expander decomposition

Cited in

(20)

• Minimum cuts and sparsification in hypergraphs
• Minimum degree orderings
• On some algorithmic aspects of hypergraphic matroids
• Hypergraph \(k\)-cut in randomized polynomial time
• Counting the number of minimum cuts in undirected multigraphs
• Minimal graph cuts on network subgraphs
• Computing All Small Cuts in an Undirected Network
• Connectivity in hypergraphs
• Using edge cuts to find Euler tours and Euler families in hypergraphs
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Breaking the barrier 2ᵏ for subset feedback vertex set in chordal graphs
• Minimum cut and minimum \(k\)-cut in hypergraphs via branching contractions
• On the sizes of vertex-k-maximal r-uniform hypergraphs
• Faster connectivity in low-rank hypergraphs via expander decomposition
• Modeling hypergraphs by graphs with the same mincut properties
• Computing minimum multiway cuts in hypergraphs
• Computing minimum multiway cuts in hypergraphs from hypertree packings
• Computing the Map of Geometric Minimal Cuts
• A Heuristic Solution of a Cutting Problem Using Hypergraphs
• Algorithms for the determination of cutsets in a hypergraph

This page was built for publication: Computing minimum cuts in hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575811)