Distance Constraint Satisfaction Problems

Abstract

We study the complexity of constraint satisfaction problems for templates $\Gamma$ that are first-order definable in $(\mathbb{Z};succ)$, the integers with the successor relation. Assuming a widely believed conjecture from finite domain constraint satisfaction (we require the tractability conjecture by Bulatov, Jeavons and Krokhin in the special case of transitive finite templates), we provide a full classification for the case that Gamma is locally finite (i.e., the Gaifman graph of $\Gamma$ has finite degree). We show that one of the following is true: The structure Gamma is homomorphically equivalent to a structure with a d-modular maximum or minimum polymorphism and $\mathrm{CSP}(\Gamma )$ can be solved in polynomial time, or $\Gamma$ is homomorphically equivalent to a finite transitive structure, or $\mathrm{CSP}(\Gamma )$ is NP-complete.

35 pages, 2 figures

References in corpus (1)

• On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction

Cited by in corpus (1)

• The complexity of disjunctive linear Diophantine constraints