Problems related to strong connectivity and strong biconnectivity

Abstract

Let $G=(V,E)$ be a strong biconnected graph and let $B\subseteq V$ such that for each vertex $w\in B$, the subgraph $G\setminus \{w\}$ is strongly connected. In this paper we study the problem of computing a subset $E_{\beta }\subseteq E$ of minimum size such that the subgraph $G_{\beta }=(V,E_{\beta })$ is strongly biconnected and for each vertex $w\in B$, the subgraph $G_{\beta }\setminus \{w\}$ is strongly connected. We prove that there exists a polynomial time $7$-approximation algorithm for this problem.