# CSPs with Few Alien Constraints

arXiv: https://arxiv.org/abs/2408.12909 · HTML: https://mlsanity.com/paper/2408.12909/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 28 references that are in the map.
- First posted on arXiv 23 Aug 2024.

## Builds on (most cited first, 2 of 2)

- [On Redundant Topological Constraints](https://mlsanity.com/paper/1403.0613/) (2014)
- [Parameterized Complexity of Equality MinCSP](https://mlsanity.com/paper/2305.11131/) (2023)

## Abstract (arXiv)

The constraint satisfaction problem asks to decide if a set of constraints over a relational structure A is satisfiable (CSP(A)). We consider CSP(A cup B) where A is a structure and 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 (mathbbN,=) (equality CSPs), together with many partial results for general ω-categorical structures.