Vertex Sparsifiers for Hyperedge Connectivity
share
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(kc^3) hyperedges that preserves all minimum cuts (up to value c) between all subset of terminals. This matches the best bound of O(kc^3) edges for normal graphs by [Liu'20(arXiv:2011.15101)]. Moreover, H can be constructed in almost-linear O(p^1+o(1) + n(rclog n)^O(rc)log m) time where r=max_e∈ 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(kc^3log^1.5(kc)) hyperedges.
READ FULL TEXT