Why there is no definition of cut vertex in directed graph?

Question

We know cut vertex is an important definition in undirected graph, indicating a vertex which when removed, the number of connected components would increase. And we also have an efficient algorithm for it.

However we don't have such counterpart definition in directed graph and I think it's natural to make an analogy: a cut vertex in a directed graph is a vertex which when removed the number of strongly connected components would increase.

Here I changed connected components to strongly connected components because it's hard to define connected component in directed graph.

It seems that people barely talk about cut vertex in directed graph, is it because this definition of cut vertex in directed graph is useless for practical usage and research purpose or because there isn't a beautiful (simple, easy-to-understand, efficient) algorithm like Tarjan's algorithm for undirected case to compute such cut vertex?

Thanks in advance!

Answer 1

Cut-points (or cut-vertices, or articulation points) in undirected graphs have a property that deleting a vertex from the graph (either cut-point or not) one may get new cut-points, but can't invalidate any existing (except the deleted one and its neighbours).

For directed graphs the vertices you are talking about are usually called strong articulation points. Removing a vertex from a directed graph one also may invalidate some other strong articulation point. Even in a directed cycle on $n$ vertices with $n$ arcs every vertex is an articulation point. But deleting any of them we invalidate all remaining. This is an essential difference and my attempt to answer the question "why?".

However there exists a linear-time algorithm which finds all strong articulation points.

Theorem 5.3. Algorithm StrongArticulationPoints computes the strong articulation points of a strongly connected graph $G$ in time $\mathrm O(m + n)$.

Also it may be interesting to look at the later survey in this topic.

Update: In undirected graph deleting a vertex may invalidate a neighboring cut-point if they share a bridge. (Initially I thought about the case when graph remains to be connected only.) But in directed case deleting a vertex may influence all other vertices of the same strong component.