Minimum $2$-vertex strongly biconnected spanning directed subgraph problem

Abstract

A directed graph $G=(V,E)$ is strongly biconnected if $G$ is strongly connected and its underlying graph is biconnected. A strongly biconnected directed graph $G=(V,E)$ is called $2$-vertex-strongly biconnected if $|V|\ge 3$ and the induced subgraph on $V\setminus \left\{w\right\}$ is strongly biconnected for every vertex $w\in V$. In this paper we study the following problem. Given a $2$-vertex-strongly biconnected directed graph $G=(V,E)$, compute an edge subset $E^{2sb}\subseteq E$ of minimum size such that the subgraph $(V,E^{2sb})$ is $2$-vertex-strongly biconnected.

References in corpus (3)

• Computing $2$-twinless blocks
• Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems
• b-articulation points and b-bridges in strongly biconnected directed graphs