3 problems

Fix an integer $d>1$. Let $\Phi=(X,Y,\Psi,W)$ be a weighted bipartite $d$-to-$1$ label-cover instance with label sets $\{1,\ldots,R\}$ and $\{1,\ldots,R/d\}$ and total edge weight…

Let $G={\rangle (V,E),2R,\Psi\langle}$ be a label-cover instance whose constraints are alpha-constraints, where an alpha-constraint is defined by permutations…

Let $\Phi$ be a $d$-to-$1$ label-cover instance: its constraints are binary, form a bipartite graph, and for each constraint every label on one variable admits one label on the oth…