Daniel Vaz, from Technical University of Munich, will give a talk entitled "Vertex Sparsification for Edge Connectivity" on 7 May.

"ALGO talks" is a seminar series organized by the ALGorithms and Optimization Lab, Adaptive Computation Group, CISUC and University of Coimbra.

Zoom:

https://videoconf-colibri.zoom.us/j/81327981104?pwd=Zkh1NWpmVE5WOGhMdWpEUWtHeUowZz09

Password: 752781

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.

Bio: Daniel Vaz is a postdoctoral researcher in the Operations Research Group at the Technical University of Munich in Germany. He obtained bachelor's and master's degrees from the University of Coimbra, and then moved to the Max Planck Institute for Informatics, where he completed his PhD on the topic of Approximation Algorithms for Network Design and Cut Problems in Bounded Treewidth. His research focuses on approximation algorithms for combinatorial optimization problems.