Abstract
We give a survey of recent results on the complexity of constraint satisfaction problems. Our main emphasis is on tractable structural restrictions.
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
Adler, I., Gottlob, G., Grohe, M.: Hypertree-width and related hypergraph invariants. In: Felsner, S. (ed.) Proceedings of the 3rd European Conference on Combinatorics, Graph Theory, and Applications. DMTCS Proceedings Series, vol. AE, pp. 5–10 (2005)
Arnborg, S., Corneil, D., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods 8, 277–284 (1987)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25, 1305–1317 (1996)
Bulatov, A.: Tractable conservative constraint satisfaction problems. In: Proceedings of the 18th IEEE Symposium on Logic in Computer Science, pp. 321–330 (2003)
Bulatov, A.: H-coloring dichotomy revisited. Theoretical Computer Science 349, 31–39 (2005)
Bulatov, A.: A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM 53, 66–120 (2006)
Bulatov, A., Krokhin, A., Jeavons, P.: The complexity of maximal constraint languages. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, pp. 667–674 (2001)
Bulatov, A., Krokhin, A., Jeavons, P.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing 34, 720–742 (2005)
Chen, H., Dalmau, V.: Beyond hypertree width: Decomposition methods without decompositions. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 167–181. Springer, Heidelberg (2005)
Chen, H., Grohe, M.: Constraint satisfaction with succinctly specified relations (in preparation)
Cohen, D., Jeavons, P.: The complexity of constraint languages. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, ch. 6. Elsevier, Amsterdam (2006)
Cohen, D., Jeavons, P., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (2005) (to appear)
Dalmau, V.: Generalized majority-minority operations are tractable. In: Proceedings of the 20th IEEE Symposium on Logic in Computer Science, pp. 438–447 (2005)
Dalmau, V., Kolaitis, P.G., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol. 2470, pp. 310–326. Springer, Heidelberg (2002)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)
Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM Journal on Computing 28, 57–104 (1998)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Proceedings of the 8th National Conference on Artificial Intelligence, pp. 4–9 (1990)
Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. Journal of Computer and System Sciences 64, 579–627 (2002)
Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, pp. 552–561 (2003)
Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: Proceedings of the of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 289–298 (2006)
Hell, P., Nešetřil, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B 48, 92–110 (1990)
Hell, P., Nešetřil, J., Zhu, X.: Complexity of tree homomorphisms. Discrete Applied Mathematics 70, 23–36 (1996)
Hell, P., Nešetřil, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. Transactions of the American Mathematical Society 348(4), 1281–1297 (1996)
Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science 200, 185–204 (1998)
Jeavons, P., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM 44(4), 527–548 (1997)
Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. In: Proceedings of the 17th ACM Symposium on Principles of Database Systems, pp. 205–213 (1998)
Ladner, R.E.: On the structure of polynomial time reducibility. Journal of the ACM 22, 155–171 (1975)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing, pp. 216–226 (1978)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grohe, M. (2006). The Structure of Tractable Constraint Satisfaction Problems. In: Královič, R., Urzyczyn, P. (eds) Mathematical Foundations of Computer Science 2006. MFCS 2006. Lecture Notes in Computer Science, vol 4162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11821069_5
Download citation
DOI: https://doi.org/10.1007/11821069_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37791-7
Online ISBN: 978-3-540-37793-1
eBook Packages: Computer ScienceComputer Science (R0)