2022/07/08 by Jiang, Han, Huang, Shang-En, Saranurak, Thatchaphol +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2207.04115
Recently, Chalermsook et al. [SODA'21(arXiv:2007.07862)] introduces a notion of vertex sparsifiers for c-edge connectivity, which has found applications in parameterized algorithms for network design and also led to exciting dynamic algorithms for c-edge st-connectivity [Jin and Sun FOCS'21(arXiv:2004.07650)]. We study a natural extension called vertex sparsifiers for c-hyperedge connectivity and construct a sparsifier whose size matches the state-of-the-art for normal graphs. More specifically, we show that, given a hypergraph G=(V,E) with n vertices and m hyperedges with k terminal vertices and a parameter c, there exists a hypergraph H containing only O(kc3) hyperedges that preserves all minimum cuts (up to value c) between all subset of terminals. This matches the best bound of O(kc3) edges for normal graphs by [Liu'20(arXiv:2011.15101)]. Moreover, H can be constructed in almost-linear O(p1+o(1) + n(rclog n)O(rc)log m) time where r=maxe∈ E|e| is the rank of G and p=∑e∈ E|e| is the total size of G, or in poly(m, n) time if we slightly relax the size to O(kc3log1.5(kc)) hyperedges.