CSPs with Few Alien Constraints
This work addresses a theoretical problem in computational complexity for researchers, providing incremental advancements in classifying CSP variants.
The paper tackles the problem of classifying the complexity of constraint satisfaction problems (CSPs) with a limited number of alien constraints, establishing connections to previously unclassified problems. It results in an FPT versus pNP dichotomy for arbitrary finite structures and sharper dichotomies for specific cases like Boolean structures and equality CSPs.
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{A} \cup \mathcal{B})$ where $\mathcal{A}$ is a structure and $\mathcal{B}$ is an alien structure, and analyse its (parameterized) complexity when at most $k$ alien constraints are allowed. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts. Our novel approach, utilizing logical and algebraic methods, yields an FPT versus pNP dichotomy for arbitrary finite structures and sharper dichotomies for Boolean structures and first-order reducts of $(\mathbb{N},=)$ (equality CSPs), together with many partial results for general $ω$-categorical structures.