Vertex Sparsifiers for Hyperedge Connectivity

Abstract

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(k{c}^3)$ hyperedges that preserves all minimum cuts (up to value $c$) between all subset of terminals. This matches the best bound of $O(k{c}^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(rc\log n{)}^{O(rc)}\log m)$ time where $r={\max }_{e\in E}|e|$ is the rank of $G$ and $p={\sum }_{e\in E}|e|$ is the total size of $G$, or in $\text{poly}(m,n)$ time if we slightly relax the size to $O(k{c}^3{\log }^{1.5}(kc))$ hyperedges.

submitted to ESA 2022