ALGO Talk - Vertex sparsification for edge connectivity

Talk by Daniel Vaz, Technical University of Munich, 3 May 2021

Abstract:

Graph compression or sparsification is a fundamental question in information theory and computer science. Given a graph with a special set of vertices called terminals, we ask if it is possible to find a smaller graph, named sparsifier, which preserves some property of the graph with respect to the terminals. A major open problem in this area is to find small sparsifiers which preserve cuts between sets of terminals, that is, sparsifiers in which the minimum cut separating any two sets of terminals is the same as in the original graph. In this talk, we look at sparsifiers for the closely related setting of c-connectivity. For a fixed value of c, a c-connectivity sparsifier preserves the number of edge-disjoint paths between any two sets of terminals, unless the number of such paths is at least c in both the original graph and the sparsifier. We show that c-connectivity sparsifiers with $O(kc^4)$ edges exist, where k is the number of terminals, and describe two algorithms for this problem: the first algorithm finds a sparsifier with $O(kc^4)$ edges in time $O(m(c \log n)^{O(c)})$, while the second finds a slightly worse sparsifier with $k O(c)^{2c}$ edges, in time $O(m c^O(c) \log^{O(1)} n)$. Our results lead to new data structures for dynamic c-connectivity problems, as well as more efficient algorithms for network design problems.