Next: MINIMUM INTERVAL GRAPH COMPLETION
Up: Subgraphs and Supergraphs
Previous: MAXIMUM K-COLORABLE INDUCED SUBGRAPH
  Index
- 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
Viggo Kann
1999-04-22