  The algebraic approach to the Constraint Satisfaction Problem (CSP) uses high
order symmetries of relational structures -- polymorphisms -- to study the
complexity of the CSP. In this paper we further develop one of the methods the
algebraic approach can be implemented, and apply it to some kinds of the CSP.
This method was introduced in our LICS 2004 paper and involves the study of the
local structure of finite algebras and relational structures. It associates
with an algebra A or a relational structure S a graph, whose vertices are the
elements of A (or S), the edges represent subsets of A such that the
restriction of some term operation of A is `good' on the subset, that is, act
as an operation of one of the 3 types: semilattice, majority, or affine. In
this paper we use this theory and consider algebras with edges from a
restricted set of types. We prove type restrictions are preserved under the
standard algebraic constructions. Then we show that if the types edges in a
relational structure are restricted, then the corresponding CSP can be solved
in polynomial time by specific algorithms. In particular, we give a new,
somewhat more intuitive proof of the Bounded Width Theorem: the CSP over
algebra A has bounded width if and only if A does not contain affine edges.
Actually, this result shows that bounded width implies width (2,3). Finally, we
prove that algebras without semilattice edges have few subalgebras of powers,
that is, the CSP over such algebras is also polynomial time. The methods and
results obtained in this paper are important ingredients of the 2017 proof of
the Dichotomy Conjecture by the author. The Dichotomy Conjecture was also
proved independently by Zhuk.
