Next:
GT36 MINIMUM INTERVAL
Up:
Subgraphs and Supergraphs
Previous:
GT34 MAXIMUM K-COLORABLE
-
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.,
|E'|
.
-
Good News:
Approximable within 1.645 [
224
].
-
Bad News:
A
PX
-complete [
224
].
-
Comment:
A
PX
-complete even if restricted to strongly connected graphs
with no cycle longer than 17.
-
Garey and Johnson:
GT33
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997