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 …

Polymorphisms, and How to Use Them Page 1 Polymorphisms, and How to Use Them Libor Barto
∗1, Andrei Krokhin2, and Ross Willard †3 1 Department of Algebra, Faculty of Mathematics and …

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 …

We investigate structural implications arising from the condition that a given directed graph
does not interpret, in the sense of primitive positive interpretation with parameters or orbits …

In 2007 it was conjectured that the Constraint Satisfaction Problem (CSP) over a constraint
language $\Gamma $ is tractable if and only if $\Gamma $ is preserved by a weak near …

An equational condition is a set of equations in an algebraic language, and an algebraic
structure satisfies such a condition if it possesses terms that meet the required equations …

This paper focuses on the algebraic theory underlying the study of the complexity and the
algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend …

In this paper we briefly survey the history of the Dichotomy Conjecture for the Constraint
Satisfaction problem, that was posed 25 years ago by Feder and Vardi. We outline some of …

This is my dissertation about digraphs ordered by pp-constructability. We study in particular
smooth digraphs, ie, digraphs without sources or sinks, tournaments and semicomplete …

Finite smooth digraphs, that is, finite directed graphs without sources and sinks, can be
partially ordered via pp-constructability. We give a complete description of this poset and, in …