Many natural combinatorial problems can be expressed as constraint satisfaction problems.
This class of problems is known to be NP-complete in general, but certain restrictions on the …

A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a
fixed template is that pp-interpretations between at most countable ω-categorical relational …

Schaefer's theorem is a complexity classification result for so-called Boolean constraint
satisfaction problems: it states that every Boolean constraint satisfaction problem is either …

We prove that an ω-categorical core structure primitively positively interprets all finite
structures with parameters if and only if some stabilizer of its polymorphism clone has a …

The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated
that such CSPs are solvable in polynomial time whenever there is no natural reduction, in …

This article is concerned with classes of relational structures that are closed under taking
substructures and isomorphism, that have the joint embedding property, and that …

There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely
bounded homogeneous structures: the first one states that tractability of the CSP of such a …

A classic result due to Schaefer Proceedings of STOC 78, ACM, 1978, pp. 216--226
classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being …

For n≧3, let (H_n,E) denote the n th Henson graph, ie, the unique countable homogeneous
graph with exactly those finite graphs as induced subgraphs that do not embed the complete …

The logic MMSNP is a restricted fragment of existential second-order logic which allows to
express many interesting queries in graph theory and finite model theory. The logic was …