Using expander graphs to find vertex connectivity
Harold N. Gabow · Journal of the ACM · 2006
The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph with n vertices, m edges and connectivity κ the time bound is O (( n + min{κ 5/2; , κ n 3/4; }) m ). This improves the previous best bound of O (( n + min{κ 3 , κ n }) m ). For an undirected graph both of these bounds hold with m replaced by κ n . Expander graphs are useful for solving the following subproblem that arises in connectivity computation: A known set R of vertices contains two large but unknown subsets that are separated by some unknown set S of κ vertices; we must find two vertices of R that are separated by S .