ON THE ALGEBRAIC STRUCTURE OF COMBINATORIAL PROBLEMS

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.