Next: MINIMUM INTERVAL GRAPH COMPLETION Up: Subgraphs and Supergraphs Previous: MAXIMUM K-COLORABLE INDUCED SUBGRAPH Index

### MINIMUM EQUIVALENT DIGRAPH

- 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., |E'|.

- Good News: Approximable within 1.645 [298].

- Bad News: APX-complete [298].

- Comment: APX-complete even if restricted to strongly connected graphs with no cycle longer than 17.

- Garey and Johnson: GT33