- INSTANCE:
Graph
,
and, for each node
*u*, a finite set of available frequencies and an integer . - SOLUTION:
A frequency allocation for
*G*, i.e., for each node*u*, a subset*S(u)*of*L(u)*such that, for all , , and, for all , . - MEASURE:
The stability number of the allocation, i.e.,
.

*Good News:*Approximable within 2 [369].*Bad News:*APX-complete [369].*Comment:*Reduction from MAXIMUM 3-SATISFIABILITY.