Sparse certificates for 2-connectivity in directed graphs

Motivated by the emergence of large-scale networks in today's applications, we show how to compute efficiently smaller subgraphs that maintain some properties of an input graph. In particular, let G be a strongly connected directed graph. We consider the problem of computing the smallest strongly connected spanning subgraph of G that maintains certain connectivity relations of G. Specifically, for 2-edge-connectivity, we consider how to maintain the maximal 2-edge-connected subgraphs (2ECS) or the 2-edge-connected components (2ECC) of G, or both the maximal 2-edge-connected subgraphs and the 2-edge-connected components (2EC). Similarly, for 2-vertex-connectivity, we consider how to maintain the maximal 2-vertex-connected subgraphs (2VCS) or the 2-vertex-connected components (2VCC) of G, or both the maximal 2-vertex-connected subgraphs and the 2-vertex-connected components (2VC). All those problems are NP-hard, and thus we are interested in approximation algorithms. Additionally, we aim at designing algorithms with a good practical performance, so that they are able to scale effectively to very large graphs. While for 2ECS and 2VCS one can obtain an approximation ratio smaller than 2 by combining previously known results, providing good approximations for the 2-edge and the 2-vertex-components case seems more challenging. Here, we present linear-time approximation algorithms that achieve the following approximation guarantees: • 4-approximation for 2ECC and 2EC, and• 6-approximation for 2VCC and 2VC.Also, augmented versions of our 2VCC algorithm computes a 6-approximation for maintaining both the 2-edge and the 2-vertex-connected components (2CC), and for maintaining all the 2-connectivity relations of G (2C), i.e., both the 2-edge and the 2-vertex-connected subgraphs and components. Moreover, we provide heuristics that improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios