Vertex Sparsifiers for Hyperedge Connectivity
Series/Report No.
Leibniz International Proceedings in Informatics, LIPIcs
Part Of
Leibniz International Proceedings in Informatics, LIPIcs
Journal Volume
244
ISBN (of the container)
978-395977247-1
ISBN
9783959772471
Date Issued
2022-09-01
Author(s)
Jiang H.
DOI
10.4230/LIPIcs.ESA.2022.70
Abstract
Recently, Chalermsook et al. [SODA'21] 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'22]. 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]. Moreover, H can be constructed in almost-linear O(p1+o(1) + n(rc log n)O(rc) logm) 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(kc3 log1.5(kc)) hyperedges.
Event(s)
30th Annual European Symposium on Algorithms, ESA 2022
Type
conference paper