2015/09/09 by Georgiadis, Loukas, Italiano, Giuseppe F., Papadopoulos, Charis +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1509.02841
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 (\textsf2EC-B); the 2-edge-connected components of G (\textsf2EC-C); both the 2-edge-connected blocks and the 2-edge-connected components of G (\textsf2EC-B-C). All three problems are NP-hard, and thus we are interested in efficient approximation algorithms. For \textsf2EC-C we can obtain a 3/2-approximation by combining previously known results. For \textsf2EC-B and \textsf2EC-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.