Summary: We present an \(O(m + n)\)-time algorithm that tests if a given directed graph is 2-vertex connected, where \(m\) is the number of arcs and \(n\) is the number of vertices. Based on this result we design an \(O(n)\)-space data structure that can compute in \(O(\log ^{2} n)\) time two internally vertex-disjoint paths from \(s\) to \(t\), for any pair of query vertices \(s\) and \(t\) of a 2-vertex connected directed graph. The two paths can be reported in additional \(O(k)\) time, where \(k\) is their total length.
For the entire collection see [Zbl 1194.68005].