Constraint graph and labeling value

A binary constraint graph consists of a finite ordinary undirected multigraph, with paired incidence slots as in Regular multigraph and normalized adjacency, a finite nonempty alphabet $\mathrm{\Sigma }$, and for each edge a relation $R_e\subseteq {\mathrm{\Sigma }}^2$ in a specified endpoint order. Reversing that order transposes the relation. Loops have two incidences and test $R_e(a,a)$. Relations are explicit Boolean tables.

For a labeling $\sigma :V\to \mathrm{\Sigma }$, ${\mathrm{val}}_{\sigma }(G)$ is the fraction of ordinary edges satisfied. Put $\mathrm{val}(G)={\max }_{\sigma }{\mathrm{val}}_{\sigma }(G)$ and ${\mathrm{UNSAT}}_{\sigma }(G)=1-{\mathrm{val}}_{\sigma }(G)$, $\mathrm{UNSAT}(G)={\min }_{\sigma }{\mathrm{UNSAT}}_{\sigma }(G)$. An edgeless graph has value one. Isolated vertices may be removed without changing value. Fractions computed using directed slots agree with edge fractions. Duplicating each ordinary edge preserves them. An explicit representation uses $O(\mathrm{\mid }V\mathrm{\mid }+\mathrm{\mid }E\mathrm{\mid }\mathrm{\mid }\mathrm{\Sigma }{\mathrm{\mid }}^2)$ table entries and endpoint names of $O(\log (\mathrm{\mid }V\mathrm{\mid }+2))$ bits.