Distance constraint satisfaction problems

Publikationstyp
Journal Article
Date Issued
2016-04-01
Sprache
English
Author(s)
Bodirsky, Manuel  
Dalmau, Victor  
Martin, Barnaby  
Mottet, Antoine  
Pinsker, Michael  
TORE-URI
http://hdl.handle.net/11420/12096
Journal
Information and computation  
Volume
247
Start Page
87
End Page
105
Citation
Information and Computation 247 : 87-105 (2016-04-01)
Publisher DOI
10.1016/j.ic.2015.11.010
Scopus ID
2-s2.0-84954288234
We study the complexity of constraint satisfaction problems for templates Γ over the integers where the relations are first-order definable from the successor function. In the case that Γ is locally finite (i.e., the Gaifman graph of Γ has finite degree), we show that Γ is homomorphically equivalent to a structure with one of two classes of polymorphisms (which we call modular max and modular min) and the CSP for Γ can be solved in polynomial time, or Γ is homomorphically equivalent to a finite transitive structure, or the CSP for Γ is NP-complete. 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), this proves that those CSPs have a complexity dichotomy, that is, are either in P or NP-complete.
Subjects
Complexity dichotomy
Constraint satisfaction problems
Endomorphisms
Integers with successor
Primitive positive definability
Reducts