Abstract
We identify a property of constraints called smoothness, and present an extremely simple randomized algorithm for solving smooth constraints. The complexity of the algorithm is much less than the lower bound for establishing path-consistency, and because smoothness is shown to be identical to connected row-convexity (CRC) for the case of binary constraints, the time and space complexity of solving CRC constraints is improved. Central to our algorithm is the relationship of smooth constraints to random walks on directed graphs. We also provide simple deterministic algorithms to test for the smoothness of a given CSP under given domain orderings of the variables. Finally, we show that some other known tractable constraint languages, like the set of implicational constraints, and the set of binary integer linear constraints, are special cases of smooth constraints, and can therefore be solved much more efficiently than the traditional time and space complexities attached with them.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bulatov, A.A., Krokhin, A.A., Jeavons, P.G.: Constraint Satisfaction Problems and Finite Algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, p. 272. Springer, Heidelberg (2000)
Cooper, M.C., Cohen, D.A., Jeavons, P.G.: Characterizing Tractable Constraints. Artificial Intelligence 65, 347–361 (1994)
Dechter, R.: Constraint Networks. In: Encyclopedia of Artificial Intelligence, 2nd edn., pp. 276–285. Wiley and Sons, Chichester (1992)
Dechter, R., Pearl, J.: Directed Constraint Networks: A Relational Framework for Causal Modeling. In: Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI 1991 (1991)
Deville, Y., Barette, O., Van Hentenryck, P.: Constraint Satisfaction over Connected Row-Convex Constraints. Artificial Intelligence 109, 243–271 (1999)
Doyle, P.G., Snell, E.J.: Random walks and Electrical Networks. In: Carus Math. Monographs 22, Math. Assoc. Amer., Washington, D. C. (1984)
Jeavons, P.G., Cohen, D.A., Cooper, M.: Constraints, Consistency and Closure. Artificial Intelligence 101, 251–265 (1998)
Jeavons, P.G.: On the Algebraic Structure of Combinatorial Problems. Theoretical Computer Science 200, 185–204 (1998)
Mohr, R., Henderson, T.C.: Arc and Path Consistency Revisited. Artificial Intelligence 28, 225–233 (1986)
Van Beek, P., Dechter, R.: On the Minimality and Global Consistency of Row-Convex Constraint Networks. Journal of the ACM (JACM) Archive 42(3), 543–561 (1995)
Van Hentenryck, P., Deville, Y., Teng, C.M.: A Generic Arc-Consistency Algorithm and its Specializations. Artificial Intelligence 57, 291–321 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Satish Kumar, T.K. (2005). On the Tractability of Smooth Constraint Satisfaction Problems. In: Barták, R., Milano, M. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2005. Lecture Notes in Computer Science, vol 3524. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11493853_23
Download citation
DOI: https://doi.org/10.1007/11493853_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26152-0
Online ISBN: 978-3-540-32264-1
eBook Packages: Computer ScienceComputer Science (R0)