2026-08-10T23:42:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17008 2024-03-06T10:58:57Z ddc:004 open_access

Vertex Sparsifiers for Hyperedge Connectivity Jiang, Han Huang, Shang-En Saranurak, Thatchaphol Zhang, Tian Vertex sparsifier hypergraph connectivity 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(kc³) hyperedges that preserves all minimum cuts (up to value c) between all subset of terminals. This matches the best bound of O(kc³) edges for normal graphs by [Liu'20]. 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³log^{1.5}(kc)) hyperedges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Han Jiang and Shang-En Huang and Thatchaphol Saranurak and Tian Zhang 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.70 urn:nbn:de:0030-drops-170081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.70 eng https://creativecommons.org/licenses/by/4.0/legalcode