Yunbum Kook (국윤범), Vertex Sparsification for Edge Connectivity

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 initiate the study of 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 contraction-based connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist by (1) introducing an extension of well-linkedness to a thresholded $c$-connectivity setting and (2) leveraging a kernelization result, based on gammoid and the representative sets lemma, to identify `essential edges’ in minimum edge cuts between a partition of terminals. We also develop an algorithm based on expander decomposition, which can find a contraction-based $c$-mimicking network of the optimal size in $m(c\log n)^{O(c)}$.

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.

This is a joint work with Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, and Daniel Vaz.