Approximating the smallest 2-vertex connected spanning subgraph of a directed graph (Q2286744): Difference between revisions

The paper considers the problem of approximating the smallest 2-vertex-connected spanning subgraph (2VCSS) of a 2-vertex-connected directed graph. A strongly connected digraph \(G\) is 2-vertex-connected if it has at least three vertices and no strong articulation points, i.e. there is no vertex \(x\) s.t. \(G \backslash x\) is not strongly connected. The previous best approximation ratio for this problem is 3/2, achieved by the algorithm by \textit{J. Cheriyan} and \textit{R. Thurimella} [SIAM J. Comput. 30, No. 2, 528--560 (2000; Zbl 1049.90104)], running in \(O(m^2)\) time. The first contribution of the paper are two linear-time algorithms that attain 3- and 2-approximate solutions, based on linear-time tests for 2-vertex-connectivity in digraphs. The 3-approximation algorithm also uses the concept of divergent spanning trees and the 2-approximation algorithm refines this approach by utilizing low-high orders. The second contribution is a new algorithm which is the result of a combination of two linear-time algorithms with the algorithm of Cheriyan and Thurimella in order to obtain a 3/2-approximation in faster \(O(m\sqrt n +n^2)\) time. A thorough experimental evaluation of all the above algorithms was conducted by the authors on a variety of input graphs. Their experimental results show the new 3/2-approximation algorithms kept essentially the same approximation ratio as the algorithm of Cheriyan and Thurimella, but it was significantly faster.