Vertex Sparsification for Edge Connectivity

Abstract

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon )$-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(k{c}^4)$ edges exist and can be found in time $m(c\log n{)}^{O(c)}$. We also give a separate algorithm that constructs such graphs with $k\cdot O(c{)}^{2c}$ edges in time $m{c}^{O(c)}{\log }^{O(1)}n$. These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c\ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

Merged version of arXiv:1910.10359 and arXiv:1910.10665 with improved bounds, 55 pages