Next:
MINIMUM INTERVAL GRAPH COMPLETION
Up:
Subgraphs and Supergraphs
Previous:
MAXIMUM K-COLORABLE INDUCED SUBGRAPH
 
Index
M
INIMUM
E
QUIVALENT
D
IGRAPH
I
NSTANCE:
Directed graph
.
S
OLUTION:
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.
M
EASURE:
Cardinality of
E'
, i.e.,
.
Good News:
Approximable within 1.645 [
315
].
Bad News:
A
PX
-complete [
315
].
Comment:
A
PX
-complete even if restricted to strongly connected graphs with no cycle longer than 17.
Garey and Johnson:
GT33
Viggo Kann
2000-03-20