Programming Research Group
Technical Report TR-8-99
New Tractable Classes From Old
David Cohen,
Richard Gault, and
Peter Jeavons
1999 24pp.
Abstract
Many combinatorial problems can be naturally expressed as ``constraint
satisfaction problems''. This class of problems is known to be NP-hard in
general, but a number of restrictions of the general problem have been
identified which ensure tractability. This paper introduces a method of
combining two or more tractable classes over disjoint domains, in order to
synthesise larger, more expressive tractable classes. We demonstrate that
the classes so obtained are genuinely novel, and have not been previously
identified. In addition, we use algebraic techniques to extend the
tractable classes which we identify, and to show that the algorithms for
solving these extended classes can be less than obvious.
This paper is available as a 112,243 byte
gzipped PostScript file.