2020/07/15 by Parinya Chalermsook, Syamantak Das, Chalermsook, Parinya +13 · 1 citation
Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.07862
openalex publication_date 2020/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1+ε)-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity-c mimicking networks with O(kc4) edges exist and can be found in time m(clog n)O(c). We also give a separate algorithm that constructs such graphs with k ⋅ O(c)2c edges in time mcO(c)logO(1)n. These results lead to the first data structures for answering fully dynamic offline c-edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.