.
such that
no two vertices in
V'
are joined by an edge in
E
.
is A
PX
-complete [
284
] and [
46
],
not approximable within
for some
[
6
], and is approximable within
for every
[
47
] and
[
46
].
For large values of
B
it is approximable within
[
155
].
Approximable within
for
k+1
-claw free graphs
[
151
].
The vertex weighted version is approximable within
3/2 for
B=3
[
167
], and within
(B+2)/3
for
B>3
[
152
].
M
AXIMUM
I
NDEPENDENT
S
ET
OF
K
-G
ONS
, the variation in which the number of pairwise independent
k
-gons (cycles of size
k
,
) is to be maximized
and where two
k
-gons are independent if any edge connecting
vertices from different
k
-gons must belong to at least one of these
k
-gons, is not approximable within 4/3 for any
. It is not in
A
PX
for any
unless NP
QP [
337
].
Viggo Kann