MAXIMUM COMPATIBLE BINARY CONSTRAINT SATISFACTION

• INSTANCE: Set $\{x_1,\ldots,x_n\}$ of variables taking values from the sets $D_1,\ldots,D_n$ respectively, binary compatibility constraints $C(x_i,x_j)\subseteq D_i\times D_j$ for $1\le i<j\le n$.

• SOLUTION: A compatible variable assignment to a subset of the variables such that for all pairs $(x_i,x_j)$ of variables in the subset, the corresponding values $(d_i,d_j)\in C(x_i,x_j)$.

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

  
  

• Bad News: Not approximable within $(\sum_i{\vert D_i\vert})^{1/4-\varepsilon }$ for any $\varepsilon >0$ [268] and [68].

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