We describe a general algebraic formulation for a wide range of combin
atorial problems including SATISFIABILITY, GRAPH COLORABILITY and GRAP
H ISOMORPHISM: in this formulation each problem instance is represente
d by a pair of relational structures, and the solutions to a given ins
tance are homomorphisms between these relational structures. The corre
sponding decision problem consists of deciding whether or not any such
homomorphisms exist. We then demonstrate that the complexity of solvi
ng this decision problem is determined in many cases by simple algebra
ic properties of the relational structures involved. This result is us
ed to identify tractable subproblems of SATISFIABILITY, and to provide
a simple test to establish whether a given set of Boolean relations g
ives rise to one of these tractable subproblems. (C) 1998-Elsevier Sci
ence B.V. All rights reserved.