Distance Constraint Satisfaction Problems

Abstract We study the complexity of constraint satisfaction problems for templates \(\it\Gamma\) that are first-order definable in \(({\mathbb Z}; {\it suc})\), 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 \(\it\Gamma\) is locally finite (i. e. , the Gaifman graph of \(\it\Gamma\) has finite degree). We show that one of the following is true: The structure \(\it\Gamma\) is homomorphically equivalent to a structure with a certain majority polymorphism (which we call modular median ) and CSP \((\it\Gamma)\) can be solved in polynomial time, or \(\it\Gamma\) is homomorphically equivalent to a finite transitive structure, or CSP \((\it\Gamma)\) is NP-complete.

Authors

• Manuel Bodirsky
• Víctor Dalmau
• Barnaby Martin
• Michael Pinsker

Keywords

No keywords are indexed for this paper.