- INSTANCE: Directed graph .
- SOLUTION:
A subset
such that, for every ordered pair of vertices ,
the graph
contains a directed path from
*u*to*v*if and only if*G*does. - MEASURE:
Cardinality of
*E'*, i.e., .

*Good News:*Approximable within 1.645 [315].*Bad News:*APX-complete [315].*Comment:*APX-complete even if restricted to strongly connected graphs with no cycle longer than 17.*Garey and Johnson:*GT33