# 2-Vertex Connectivity in Directed Graphs

arXiv: https://arxiv.org/abs/1409.6277 · HTML: https://mlsanity.com/paper/1409.6277/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Sep 2014.

## Built on by (most cited first, 1 of 1)

- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)

## Abstract (arXiv)

We complement our study of 2-connectivity in directed graphs, by considering the computation of the following 2-vertex-connectivity relations: We say that two vertices v and w are 2-vertex-connected if there are two internally vertex-disjoint paths from v to w and two internally vertex-disjoint paths from w to v. We also say that v and w are vertex-resilient if the removal of any vertex different from v and w leaves v and w in the same strongly connected component. We show how to compute the above relations in linear time so that we can report in constant time if two vertices are 2-vertex-connected or if they are vertex-resilient. We also show how to compute in linear time a sparse certificate for these relations, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-vertex-connectivity and vertex-resilience relations as the input graph, where n is the number of vertices.