CSPs with Few Alien Constraints

Peter Jonsson, Victor Lagerkvist, George Osipov

The constraint satisfaction problem asks to decide if a set of constraints over a relational structure $\mathcal{A}$ is satisfiable (CSP$(\mathcal{A})$). We consider CSP$(\mathcal{…