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 when $E\mathrm{\ne }\mathrm{\varnothing }$, and is defined to be $1$ when $E=\mathrm{\varnothing }$. 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)$. Thus an edgeless graph has value one and unsatisfiability zero for every labeling. Isolated vertices may be removed without changing value. Fractions computed using directed slots agree with edge fractions when $E\mathrm{\ne }\mathrm{\varnothing }$. 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.