![Calvin Lab Placeholder Image / Bruce Damonte](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-09/CalvinLab_Photo%C2%A9BruceDamonte_04%20copy.jpg?h=34bbd072&itok=mDo680N8)
Abstract
Vertex connectivity is a classic graph-theoretic notion that roughly measures the robustness of a graph against node failures. A classic open problem, asked by Aho, Hopcroft and Ullman in 1975, is whether or not vertex connectivity can be computed in linear time. In this short talk, I will give a quick survey on exciting developments on fast vertex connectivity algorithms in the past few years (since 2019) that culminate in a celebrated "poly-log max-flows" algorithm, leading to an almost linear time vertex connectivity algorithm by a recent breakthrough in max-flow algorithm.