Finding biconnected components (cut vertices) with a special property of a directed graph

directed graphsgraph theory

I'd like to find vertices of a directed graph such that it divides the graph into (at least) two in a special way. The successors of a vertex must be only reachable from its predecessors through the specified vertex.

Let me illustrate. Here's a directed graph with all edges directed towards from left to right.

Z      C - D - E
      /   /
A - B - F - G
 \
  H - I

Disregarding root and leaf vertices and the isolated vertex $Z$ that trivially fit the criteria, the vertices that I'm looking for are: $B$, $D$ and $H$.

For a graph containing cycles:

      3 - 4 - 6
     /     \
1 - 2 <---- 5

The vertices I'm looking for are $2$ and $4$. $2$ is the waypoint for access from $1$, and $4$ restricts access to $6$. When it comes to other vertices in the cycle, each could fit the criteria, but as in the case for leaves and roots above, I'm not really interested in them. I would prefer if they were left out, but having them fit is not the worst thing in the world.

Here's my attempt at understanding the properties of such vertices. Biconnected components or cut vertices of a graph determine the vertices whose removal increases the number of connected components. This is too broad of a property, since vertices like $F$ that leave one unconnected component are included but its successor $D$ can be reached through $C$. Conversely, requiring a vertex to only contain bridges as outgoing edges is too strict, since in $B$ the later vertices form a diamond shape.

In my experience often it's simply a matter of finding a name for the thing I'm looking for. So if one exists, what is it? If not, could there be an elegant way of formulating the property I've described, without requiring an implementation to loop through the graph a bunch.

Best Answer

Here's my attempt. It was quite self-evident, almost said in the question, but here it is.

On a similarly connected undirected graph, we remove each vertex one at a time. For that vertex to fit the criteria, each direct predecessor must be unconnected with each direct successor.

This criteria also leaves bare cycles out, which was what I wanted. By also requiring that a vertex has predecessors and successors, roots and leaves are left out as well.

Implementing such criteria seems to be possible quite elegantly by determining the connected components of the undirected graph after deleting the vertex. Each component must never simultaneously contain a vertex from the set of predecessor vertices and a vertex from the set of successor vertices.

Related Question