Why there is no definition of cut vertices or articulation points in directed graphs?

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!

• codeR: Why would it be difficult to compute? Given a graph $G =(V, E),ドル just test for each vertex $v\in V$ whether the number of strongly connected components increases in $G' = (V\setminus \{v\}, E)$. There can be a better and more efficient way to do this as well; nevertheless, this is polynomial time doable.
• 27rabbit: Sorry, I should have put it more clearly. I mean tehre might not be a simple, easy-to-understand and efficient algorithm like Tarjan algorithm for undirected case.

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.

• 27rabbit: Thanks so much!! It definitely answered my question. Also thanks to your reference~