On the algebraic structure of combinatorial problems

We describe a general algebraic formulation for a wide range of combinatorial problems including SATISFIABILITY, GRAPH COLORABILITY and GRAPH ISOMORPHISM: in this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of SATISFIABILITY, and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems. (C) 1998-Elsevier Science B.V. All rights reserved.