Using expander graphs to find vertex connectivity

The (vertex) connectivity K 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 kappa. For a digraph with n vertices, m edges and connectivity kappa the time bound is O((n + min{kappa(5/2), kappa n(3/4)})m). This improves the previous best bound of O((n + min{kappa(3), kappa n})m). For an undirected graph both of these bounds hold with m replaced by kappa 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 kappa vertices; we must find two vertices of R that are separated by S.