Manuel Bodirsky
Constraint Satisfaction with Countable Homogeneous Templates
With Jaroslav Nesetril. Journal of Logic and Computation (JLC), 16(3), pages 359-373, 2006. An earlier version appeared in the Proceedings of Computer Science Logic and the 8th Kurt Goedel Colloquium, pages 44-57, LNCS 2803.
Abstract
For a fixed countable homogeneous relational structure Gamma - called template - we study the computational problem whether a given finite structure of the same signature homomorphically maps to Gamma. This problem is known as the constraint satisfaction problem CSP(Gamma) for Gamma and was intensively studied for finite Gamma. We show that - as in the case of finite Gamma - the computational complexity of CSP(Gamma) for countable homogeneous Gamma is determinded by the clone of polymorphisms of Gamma. To this end we prove the following theorem which is of independent interest: The primitive positive definable relations over an omega-categorical structure Gamma are precisely the relations that are invariant under the polymorphisms of Gamma. Constraint satisfaction with countable homogeneous templates is a proper generalization of constraint satisfaction with finite templates. If the age of Gamma is finitely axiomatizable, then CSP(Gamma) is in NP. If Gamma is a digraph we can use the classification of homogeneous digraphs by Cherlin to determine the complexity of CSP(Gamma).
Download
Free download of the article in pdf format is possible from the Oxford University Press site.
Remarks on Related Papers
The Galois connection between primitive positive definability and polymorphism clones for omega-categorical structures that is presented in this paper has been used extensively in later papers, for example for temporal constraint satisfaction problems and for maximal constraint languages. Also see my survey on Constraint Satisfaction Problems with Infinite Templates.
