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

Abstract

Wu and Grumbach introduced the concept of strongly biconnected directed graphs. A directed graph $G=(V,E)$ is called strongly biconnected if the directed graph $G$ is strongly connected and the underlying undirected graph of $G$ is biconnected. A strongly biconnected directed graph $G=(V,E)$ is said to be $2$- edge strongly biconnected if it has at least three vertices and the directed subgraph $(V,E\setminus \left\{e\right\})$ is strongly biconnected for all $e\in E$. Let $G=(V,E)$ be a $2$-edge-strongly biconnected directed graph. In this paper we study the problem of computing a minimum size subset $H\subseteq E$ such that the directed subgraph $(V,H)$ is $2$- edge strongly biconnected.