2017/03/10 by Chandra Chekuri, Chao Xu, Chekuri, Chandra +1
Computer Science · Decision Sciences · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Fuzzy and Soft Set Theory #Limits and Structures in Graph Theory #Mathematical Approximation and Integration #cs.DS
paper · pdf · doi:10.48550/arxiv.1703.03849
arxiv created 2017/03/10 · openalex publication_date 2017/03/10 · arxiv updated 2017/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let H=(V,E) be an edge-weighted hypergraph of rank r. Kogan and Krauthgamer extended Benczúr and Karger's random sampling scheme for cut sparsification from graphs to hypergraphs. The sampling requires an algorithm for computing the approximate strengths of edges. In this note we extend the algorithm for graphs to hypergraphs and describe a near-linear time algorithm to compute approximate strengths of edges; we build on a sparsification result for hypergraphs from our recent work. Combined with prior results we obtain faster algorithms for finding (1+ε)-approximate mincuts when the rank of the hypergraph is small.