Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs

Olivier Fischer, Yonggang Jiang, Sagnik Mukhopadhyay +1

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 varian…