Approximable within
for k+1-claw free graphs
[209].
The vertex weighted version is approximable within
3/2 for
[231], within
for
[205], and within
for larger values of
[211].
The related problem in hypergraphs is approximable within
[211], also in the weighted case.
MAXIMUM INDEPENDENT SET OF K-GONS, 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
APX for any
unless NP
QP [434].