Next:
GT31 MAXIMUM K-COLORABLE
Up:
Subgraphs and Supergraphs
Previous:
GT29 MAXIMUM PLANAR
GT30 M
INIMUM
E
DGE
D
ELETION
K
-
PARTITION
I
NSTANCE
: Graph
and a weight function
.
S
OLUTION
: An
k
-partition, i.e., a color assignment
.
M
EASURE
: The weight of the monochromatic edges, i.e.,
.
Good News:
Approximable within
for
k=2
[
128
] and within
for
k=3
and any
[
204
].
Bad News:
A
PX
-hard [
128
].
Comment:
Not approximable within 1.058 for
k=2
[
164
]. Not approximable within
O(|E|)
for
, even for graphs with
for any
[
204
]. Approximable within 9/4 for planar graphs and
k=2
[
136
].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997