Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs

Let $G$ be a strongly connected directed graph. We consider the following three problems, where we wish to compute the smallest strongly connected spanning subgraph of $G$ that maintains respectively: the $2$-edge-connected blocks of $G$ ($\mathsf{\text{2EC-B}}$); the $2$-edge-connected components of $G$ ($\mathsf{\text{2EC-C}}$); both the $2$-edge-connected blocks and the $2$-edge-connected components of $G$ ($\mathsf{\text{2EC-B-C}}$). All three problems are NP-hard, and thus we are interested in efficient approximation algorithms. For $\mathsf{\text{2EC-C}}$ we can obtain a $3\mathrm{/}2$-approximation by combining previously known results. For $\mathsf{\text{2EC-B}}$ and $\mathsf{\text{2EC-B-C}}$, we present new $4$-approximation algorithms that run in linear time. We also propose various heuristics to improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios.