Approximating the minimum strongly connected subgraph via a matching lower bound

ABSTRACT

We present a 3/2-approximation algorithm for the problem of finding a minimum strongly connected spanning subgraph in a given directed graph. As a corollary we obtain a 3/2-approximation algorithm for the more general minimum equivalent digraph problem. The performance of our algorithm is measured against a lower bound obtained from a simple matching problem. The performance guarantee is optimal with respect to the lower bound.

REFERENCES

• 1: Harry T. Hsu, An Algorithm for Finding a Minimal Equivalent Graph of a Digraph, Journal of the ACM (JACM), v.22 n.1, p.11-16, Jan. 1975 [doi>10.1145/321864.321866]
• 2: Samir Khuller , Balaji Raghavachari , Neal Young, Approximating the Minimum Equivalent Digraph, SIAM Journal on Computing, v.24 n.4, p.859-872, Aug. 1995 [doi>10.1137/S0097539793256685]
• 3: Samir Khuller , Balaji Raghavachari , Neal Young, On strongly connected digraphs with bounded cycle length, Discrete Applied Mathematics, v.69 n.3, p.281-289, Aug. 27, 1996 [doi>10.1016/0166-218X(95)00105-Z]
• 4: Dennis M. Moyles , Gerald L. Thompson, An Algorithm for Finding a Minimum Equivalent Graph of a Digraph, Journal of the ACM (JACM), v.16 n.3, p.455-460, July 1969 [doi>10.1145/321526.321534]
• 5: Santosh Vempala , Adrian Vetta, Factor 4/3 approximations for minimum 2-connected subgraphs, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.262-273, September 05-08, 2000

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Performance, Theory, Verification