## neal young / Khuller95Approximating

• 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/6 ~ 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].) The 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].

© Copyrights are reserved by the publishers.