Recent Advances in Vertex Connectivity ProblemsLecture

by Dr Sorrachai Yingchareonthawornchai

Tuesday Nov 11, 2025, 9:00 AM → 9:45 AM Europe/Berlin

Endenicher Allee 60/1-016 - Lipschitzsaal (Mathezentrum)

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. Despite a lot of research effort in the past decades, state-of-the-art algorithms were far from being linear time.  In this talk, I present a brief survey of exciting developments in fast vertex connectivity algorithms in the past few years that culminate in the development of a celebrated 'poly-log max-flows' algorithm, leading to an almost linear time vertex connectivity algorithm due to the recent breakthrough in max-flow algorithms. This answers the long-standing open problem by Aho, Hopcroft, and Ullman, and opens new research directions towards computing vertex connectivity in different setting such as derandomization, parallel algorithms, vertex connectivity augmentation, and many others.