Next: SHORTEST PATH MOTION IN Up: Miscellaneous Previous: MINIMUM SORTING BY REVERSALS Index

### MAXIMUM COMPATIBLE BINARY CONSTRAINT SATISFACTION

- INSTANCE: Set of variables taking values from the sets respectively, binary compatibility constraints for .

- SOLUTION: A compatible variable assignment to a subset of the variables such that for all pairs (xi,xj) of variables in the subset, the corresponding values .

- MEASURE: The number of variables in the compatible variable assignment.

- Bad News: Not approximable within for any [253] and [63].

- Comment: Equivalent to MAXIMUM CLIQUE under PTAS-reduction [253].