Faster Deterministic Vertex Connectivity Algorithms

In this talk, I will describe a deterministic algorithm for checking $k$-vertex connectivity in time proportional to making $\min\{k^2, n\}$ max-flow calls, and, hence, in $\widehat{O}(m\min\{k^{2},n\})$ time using the deterministic max-flow algorithm by [Brand~et~al.~FOCS'23]. Our algorithm gives the first almost-linear-time bound for all $k$ where $\sqrt{\log n}\le k\le n^{o(1)}$ and subsumes up to a sub-polynomial factor the long-standing state-of-the-art algorithm by [Even'75] which requires $O(n+k^{2})$ max-flow calls. For large $k$, the algorithm runs in $\widehat O(mn)$ time, which improves over the state-of-the-art deterministic $\widehat{O}(mn^{1.5})-time algorithm~[Gabow, FOCS'00].

Our key technique is based on Ramanujan expanders and derandomization of the kernelization technique of [Li~et~al.~STOC'21] for which their kernel construction was randomized.

Joint work with Yonggang Jiang, Chaitanya Nalam, and Thatchaphol Saranurak.