I
NSTANCE
:
Set
of variables taking values from the sets
respectively, binary compatibility constraints
for
.
S
OLUTION
:
A compatible variable assignment to a subset of the variables such that
for all pairs
of variables in the subset, the corresponding
values
.
M
EASURE
:
The number of variables in the compatible variable assignment.
Bad News:
Not approximable within
for any
[
187
] and [
40
].
Comment:
Equivalent to M
AXIMUM
C
LIQUE
under PTAS-reduction [
187
].