Faster connectivity in low-rank hypergraphs via expander decomposition

DOI10.1007/978-3-031-06901-7_6MaRDI QIDQ2164680zbMATH OpenOpenAlexFDO

Authors Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay, Danupon Nanongkai

Publication date 16 August 2022

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

zbMATH Keywords

connectivityexpander decompositionhypergraphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Abstract: We design an algorithm for computing connectivity in hypergraphs which runs in time $hat{O}_r(p+minlambd{a}^{fracr-3r-1}{n}^2,n^r/lambd{a}^{r/(r-1)})$ (the $hat{O}_r(cdot)$ hides the terms subpolynomial in the main parameter and terms that depend only on $r$) where $p$ is the size, $n$ is the number of vertices, and $r$ is the rank of the hypergraph. Our algorithm is faster than existing algorithms when the the rank is constant and the connectivity $lambda$ is $omega(1)$. At the heart of our algorithm is a structural result regarding min-cuts in simple hypergraphs. We show a trade-off between the number of hyperedges taking part in all min-cuts and the size of the smaller side of the min-cut. This structural result can be viewed as a generalization of a well-known structural theorem for simple graphs [Kawarabayashi-Thorup, JACM 19]. We extend the framework of expander decomposition to simple hypergraphs in order to prove this structural result. We also make the proof of the structural result constructive to obtain our faster hypergraph connectivity algorithm.

Recommendations

• Minimum cuts and sparsification in hypergraphs
• Computing minimum cuts in hypergraphs
• Minimum cut and minimum k-cut in hypergraphs via branching contractions
• Using expander graphs to find vertex connectivity
• Hypergraph \(k\)-cut in randomized polynomial time

Cites work

• A fast hypergraph min-cut algorithm for circuit partitioning
• A new approach to the minimum cut problem
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Computing exact minimum cuts without knowing the graph
• Computing minimum cuts in hypergraphs
• Deterministic Edge Connectivity in Near-Linear Time
• Deterministic global minimum cut of a simple graph in near-linear time
• Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
• Expander decomposition and pruning: faster, stronger, and simpler
• Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
• Fully-dynamic minimum spanning forest with improved worst-case update time
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 6850403 (Why is no real title available?)
• Local flow partitioning for faster edge connectivity
• Minimizing symmetric submodular functions
• Minimum cut and minimum k-cut in hypergraphs via branching contractions
• Minimum cuts and sparsification in hypergraphs
• Minimum cuts in near-linear time
• Random contractions and sampling for hypergraph and hedge connectivity
• Sketching cuts in graphs and hypergraphs
• Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search
• Vertex connectivity in poly-logarithmic max-flows
• Weighted min-cut: sequential, cut-query, and streaming algorithms

Cited in

(4)

• Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
• Minimum cuts and sparsification in hypergraphs
• Computing minimum cuts in hypergraphs
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions

This page was built for publication: Faster connectivity in low-rank hypergraphs via expander decomposition

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