Characterising tractable constraints

摘要

Finding solutions to a binary constraint satisfaction problem is known to be an NP-complete problem in general, but may be tractable in cases where either the set of allowed constraints or the graph structure is restricted. This paper considers restricted sets of constraints which are closed under permutation of the labels. We identify a set of constraints which gives rise to a class of tractable problems and give polynomial time algorithms for solving such problems, and for finding the equivalent minimal network. We also prove that the class of problems generated by any set of constraints not contained in this restricted set is NP-complete.