The MEG (minimum equivalent graph) problem is, given a
directed graph, to find a small subset of the edges that
maintains all reachability relations between nodes. The
problem is NP-hard. This paper gives an approximation
algorithm with performance guarantee of pi2
1.64. The algorithm and its analysis are based on the simple
idea of contracting long cycles.
(This result was strengthened
slightly in ``On strongly connected digraphs with bounded
cycle length'' [1996
analysis applies directly to 2-Exchange, a simple local
improvement algorithm, showing that its performance
guarantee is 1.75.
It was further improved by Berman et al, WADS 2009
Journal version of [1994