In my PhD-thesis in 2004, I posed 19 questions related to the complexity of infinite-domain constraint satisfaction; 16 remain open. Here is a report about progress on these problems. More background for the problems mentioned here can be found in Section 7.4 of my thesis.

*Which structures that are interpretable in the dense linear order of the rational numbers (Q,<) have tractable constraint satisfaction problems?*

Status is still open. If * interpretable * is replaced
by * definable * (by which I mean first-order definable without parameters) the problem has been
solved.
Note that all finite structures are
interpretable in every structure with more than one element, so a solution would also yield
a description of the tractable CSPs over finite domains.

* Which structures interpretable in the omega-categorical, unbounded, dense, and binary branching semilinear order have tractable constraint satisfaction problems?*

This is open even if 'interpretable' is replaced by 'definable'. Already there we find many concrete problems that have been studied independently in artificial intelligence ('branching time constrains'), computational biology ('phylogenetic reconstruction'), and computational linguistics ('tree description constraints').

* What are the polymorphisms of the structure with all binary relations that are first-oder definable the semi-linear order described in Question 2?*

Open. (The formulation is slightly different from the version in my thesis to make it more clear.)

* Let N be a finite set of relational structures, and let Forb(N) be the set of all finite structures that do not embed a structure from N. When is Forb(N) an amalgamation class? *

Open.

* Let Q be a set of structures that is closed under taking disjoint unions. Is it true that Q is in monotone SNP if and only if it can be described as CSP(Gamma) where Gamma is a finitely constrained omega-categorical structure? *

Trivially false: CSP(Z,succ), where succ is the binary successor relation over the integers, cannot be formulated with an omega-categorical template (see On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction) but is clearly in monotone SNP.

* Let Gamma be a finitely constrained homogeneous tau-structure. Given a first-order formula over signature tau, is it decidable whether the formula is on Gamma equivalent to a primitive positive formula?*

Open in general. But strong partial results can be found in Decidability of Definability.

* Is there a constraint satisfaction problem with
an omega-categorical template which is tractable, but not globally tractable?*

To entirely formalize this question, one would have to specify how to represent the relations from the infinite signature in the input. The formulation in the thesis by mistake also requires that Gamma is finitely constrained. What was actually meant is that all relations of Gamma are first-order definable over some finitely constrained homogeneous structure with the same domain. For such structures there is a natural representation for the relations in the input. The question is still open for those structures.

* For which sets N of finite graphs (or, more generally, structures over a finite signature) the almost-sure theory of Forb(N) is omega-categorical? *

Open as far as I know.

*Let N be a finite set of finite structures such that Forb(N) is an amalgamation class, and let Gamma be its Fraisse-limit. Is it decidable whether CSP(Gamma) has width k, or bounded width? *

Open.

* Is there an omega-categorical CSP which has bounded width k for k larger than 2, but does not have width 2? *

Yes (to appear).

* Given a finitely constrained omega-categorical structure Gamma, is it decidable whether CSP(Gamma) has bounded strict width? *

Even though a universal-algebraic characterization of bounded strict width exists (also see these applications) its decidability is still open. However, using this in combination with Decidability of Definability we get decidability in many cases.

* Is 'Consistent Genealogy', i.e., the CSP for the binary relations definable in the unbounded dense semilinear ordering, solvable by Datalog? *

Solved: the answer is negative, see Rooted Phylogeny Problems.

* Let Gamma be an omega-categorical structure with a finite relational signature, where Pol(Gamma) contains a Maltsev operation. Is CSP(Gamma) tractable? *

Solved: if Gamma has a Maltsev polymorphism (actually, a quasi Maltsev suffices), then its model-complete core also has a quasi-Maltsev operation. But, as shown in this paper, the model-complete core of such a structure must be finite, so the CSP is in P by the algorithm of Bulatov and Dalmau.

* For which MMSNP(\neq)-sentences on graphs the model-checking problem is NP-hard?*

This is un undecidable property so we cannot hope for an answer here.

* Let H be an infinite graph. Is it true that CSP(H) is either in P or NP-hard?*

For directed graphs, the answer is no (and for undirected graphs I strongly conjecture that it is false as well).

* Is every surjective homomorphism problem computationally equivalent to a finitely constrained CSP?*

Open.

* Which finite structures have tractable surjective homomorphism problems?*

Open, probably very difficult. The first problems of open computational complexity appear for domain size three (see below). But this problem is also open for the six-cycle (an undirected graph).

* Is the 3-partition problem NP-hard?*

Open. The 3-partition problem asks whether we can find for a given ternary relation R on a finite set V a partition of V into three non-empty sets A,B,C such that for every tuple (x,y,z) from R either x,y,z lie in the same part, or x is from A, y is from B, and z is from C.

* Is the no-rainbow-coloring problem NP-hard?*

Open. The no-rainbow problem asks whether a given 3-uniform hypergraph on vertex set V can be partitioned into three non-empty subsets A,B,C of V such that no edge is 'rainbow-colored', i.e., contains one vertex from each of A,B,C.