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.
Supported by an EPSRC grant, number GR/M12926.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Bjäreland and P. Jonsson. Exploiting bipartiteness to identify yet another tractable subclass of CSP. In J. Jaffar, editor, Principles and Practice of Constraint Programming-CP’99, number 1713 in Lecture Notes in Computer Science, pages 118–128. Springer, 1999.
A. A. Bulatov, A. A. Krokhin, and P. Jeavons. Constraint satisfaction problems and finite algebras. Technical Report TR-4-99, Oxford University Computing Laboratory, 1999.
A. A. Bulatov, A. A. Krokhin, and P. Jeavons. Constraints over a three-element domain: tractable maximal relational clones. Unpublished Manuscript, 1999.
D. Cohen, P. Jeavons, and M. Koubarakis. Tractable disjunctive constraints. In Proceedings 3rd International Conference on Constraint Programming-CP’96 (Linz, October 1997), volume 1330 of Lecture Notes in Computer Science, pages 478–490. Springer-Verlag, 1996.
P. Cohn. Universal Algebra. Herper & Row, 1965.
M. Cooper, D. Cohen, and P. Jeavons. Characterising tractable constraints. Artificial Intelligence, 65:347–361, 1994.
V. Dalmau. A new tractable class of constraint satisfaction problems. In 6th International Symposium on Mathematics and Artificial Intelligence, 2000.
V. Dalmau and J. Pearson. Closure functions and width 1 problmes. In J. Jaffar, editor, Principles and Practice of Constraint Programming-CP’99, number 1713 in Lecture Notes in Computer Science, pages 159–173. Springer, 1999.
R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, 38:353–366, 1989.
E. Freuder. A sufficient condition for backtrack-bounded search. Journal of the ACM, 32:755–761, 1985.
M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA., 1979.
P. Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200:185–204, 1998.
P. Jeavons and D. Cohen. An algebraic characterization of tractable constraints. In Computing and Combinatorics. First International Conference COCOON’95 (Xi’an, China, August 1995), volume 959 of Lecture Notes in Computer Science, pages 633–642. Springer-Verlag, 1995.
P. Jeavons, D. Cohen, and M. Gyssens. A unifying framework for tractable constraints. In Proceedings 1st International Conference on Constraint Programming-CP’95 (Cassis, France, September 1995), volume 976 of Lecture Notes in Computer Science, pages 276–291. Springer-Verlag, 1995.
P. Jeavons, D. Cohen, and M. Gyssens. A test for tractability. In Proceedings 2nd International Conference on Constraint Programming-CP’96 (Boston, August 1996), volume 1118 of Lecture Notes in Computer Science, pages 267–281. Springer-Verlag, 1996.
P. Jeavons, D. Cohen, and M. Gyssens. Closure properties of constraints. Journal of the ACM, 44:527–548, 1997.
P. Jeavons and M. Cooper. Tractable constraints on ordered domains. Artificial Intelligence, 79(2):327–339, 1995.
L. Kirousis. Fast parallel constraint satisfaction. Artificial Intelligence, 64:147–160, 1993.
P. Ladkin and R. Maddux. On binary constraint problems. Journal of the ACM, 41:435–469, 1994.
A. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99–118, 1977.
R. McKenzie, G. McNulty, and W. Taylor. Algebras, Lattices and Varieties, volume I. Wadsworth and Brooks, California, 1987.
U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences, 7:95–132, 1974.
B. Nebel and H.-J. Burckert. Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra. Journal of the ACM, 42:43–66, 1995.
T. Schaefer. The complexity of satisfiability problems. In Proceedings 10th ACM Symposium on Theory of Computing (STOC), pages 216–226, 1978.
P. van Beek and R. Dechter. On the minimality and decomposability of row-convex constraint networks. Journal of the ACM, 42:543–561, 1995.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cohen, D., Jeavons, P., Gault, R. (2000). New Tractable Classes from Old. In: Dechter, R. (eds) Principles and Practice of Constraint Programming – CP 2000. CP 2000. Lecture Notes in Computer Science, vol 1894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45349-0_13
Download citation
DOI: https://doi.org/10.1007/3-540-45349-0_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41053-9
Online ISBN: 978-3-540-45349-9
eBook Packages: Springer Book Archive