not quite biconnected component in DAGs

49 Views Asked by At

In undirected graphs, a "biconnected component" is a maximal subgraph containing no cut-vertices, that is, vertices whose deletion increases the number of connected components.

For directed graphs, I have the impression that people usually apply the definition above to the underlying undirected graph. However, I am looking for something similar, yet not quite the same:

Given a DAG G, a vertex x is a not-quite-cut-vertex iff for all strict ancestors s of x in G and all strict descendants t of x in G, all s-t-paths in G contain x. Further, a not-quite-biconnected-component of G is a maximal subgraph that is weakly connected and does not have a not-quite-cut-vertex.

In particular, the DAG G=({a,b,c,d,e},{ac,ad,bc,be,cd,ce}) has 2 biconnected components but only 1 not-quite-biconnected-component (since c is a cut-vertex but not a not-quite-cut-vertex).

The questions are now: Is this concept known for digraphs/DAGs? Is the decomposition into not-quite-biconnected-components unique? What is the complexity of computing the not-quite-biconnected-components?