Characterising tractable constraints

✍ Scribed by Martin C. Cooper; David A. Cohen; Peter G. Jeavons

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 672 KB
• Volume: 65
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(94)90021-3

✦ Synopsis

Cooper, M.C., D.A. Cohen and P.G. Jeavons, Characterising tractable constraints (Research Note), Artificial Intelligence 65 (1994) 347-361.

Finding solutions to a binary constraint satisfaction problem is known to be an NPcomplete 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.