Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Vertex connectivity and its variants are among the most fundamental problems in graph theory, with decades of extensive study and numerous algorithmic advances. The directed variants of vertex connectivity are usually solved by manually extending fast algorithms for undirected graphs, which has required considerable effort. In this paper, we present an extremely simple reduction from directed to undirected vertex connectivity for dense graphs. As immediate corollaries, we vastly simplify the proof for directed vertex connectivity in \(n^{2+o(1)}\) time [25], and obtain a parallel vertex connectivity algorithm for directed graphs with \(n^{\omega+o(1)}\) work and \(n^{o(1)}\) depth, via the undirected vertex connectivity algorithm of [4].