Next:
GT30 MINIMUM EDGE
Up:
Subgraphs and Supergraphs
Previous:
GT28 MAXIMUM DEGREE-BOUNDED
-
I
NSTANCE
:
Graph
.
-
S
OLUTION
:
A subset
such that
is planar.
-
M
EASURE
:
Size of the subset, i.e.,
|E'|
.
-
Good News:
Approximable within 2.5 [
61
].
-
Bad News:
A
PX
-complete [
61
].
-
Comment:
Transformation from M
INIMUM
M
ETRIC
T
RAVELING
S
ALESPERSON
P
ROBLEM
with distances one and two.
The complementary problem
Minimum Nonplanar Edge Deletion
is
A
PX
-hard.
Variation in which the subgraph should be outerplanar is A
PX
-complete and
approximable within 1.5 [
61
].
-
Garey and Johnson:
GT27
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997