Abstract
A wide range of problems can be modelled as constraint satisfaction problems (CSPs), that is, a set of constraints that must be satisfied simultaneously. Constraints can either be represented extensionally, by explicitly listing allowed combinations of values, or implicitly, by special-purpose algorithms provided by a solver. Such implicitly represented constraints, known as global constraints, are widely used; indeed, they are one of the key reasons for the success of constraint programming in solving real-world problems. In recent years, a variety of restrictions on the structure of CSP instances have been shown to yield tractable classes of CSPs. However, most such restrictions fail to guarantee tractability for CSPs with global constraints. We therefore study the applicability of structural restrictions to instances with such constraints. We show that when the number of solutions to a CSP instance is bounded in key parts of the problem, structural restrictions can be used to derive new tractable classes. Furthermore, we show that this result extends to combinations of instances drawn from known tractable classes, as well as to CSP instances where constraints assign costs to satisfying assignments.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adler, I. (2006). Width functions for hypertree decompositions. Doctoral dissertation, Albert-Ludwigs-Universität Freiburg.
Adler, I., Gottlob, G., Grohe, M. (2007). Hypertree width and related hypergraph invariants. European Journal of Combinatorics, 28(8), 2167–2181. doi:10.1016/j.ejc.2007.04.013. http://www.sciencedirect.com/science/article/pii/S0195669807000753.
Aschinger, M., Drescher, C., Friedrich, G., Gottlob, G., Jeavons, P., Ryabokon, A., Thorstensen, E. (2011). Optimization methods for the partner units problem. In Proceedings of the 8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR’11), Lecture Notes in Computer Science, (Vol. 6697 pp. 4–19). Berlin: Springer.
Aschinger, M., Drescher, C., Gottlob, G., Jeavons, P., Thorstensen, E. (2011). Structural decomposition methods and what they are good for. In Schwentick, T., & Dürr, C. (Eds.) Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS’11), Leibniz International Proceedings in Informatics, (Vol. 9 pp. 12–28). doi:10.4230/LIPIcs.STACS.2011.12. http://drops.dagstuhl.de/opus/volltexte/2011/2996.
Atserias, A., Grohe, M., Marx, D. (2013). Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4), 1737–1767. doi:10.1137/110859440.
Bessiere, C., Hebrard, E., Hnich, B., Walsh, T. (2007). The complexity of reasoning with global constraints. Constraints, 12(2), 239–259. doi:10.1007/s10601-006-9007-3.
Bessiere, C., Katsirelos, G., Narodytska, N., Quimper, C.G., Walsh, T. (2010). Decomposition of the NValue constraint. In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP’10), Lecture Notes in Computer Science, (Vol. 6308) . Berlin: Springer.
Bulatov, A., Jeavons, P., Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3), 720–742. doi:10.1137/S0097539700376676 . http://link.aip.org/link/?SMJ/34/720/1.
Chen, H., & Grohe, M. (2010). Constraint satisfaction with succinctly specified relations. Journal of Computer and System Sciences, 76(8), 847–860. doi:10.1016/j.jcss.2010.04.003. http://www.sciencedirect.com/science/article/pii/S0022000010000450.
Cohen, D., & Green, M. (2006). Typed guarded decompositions for constraint satisfaction. In Benhamou, F. (Ed.) Proceedings of the 12th International Conference on the Principles and Practice of Constraint Programming (CP’06), Lecture Notes in Computer Science, (Vol. 4204 PP. 122–136). Berlin: Springer. doi:10.1007/11889205_11.
Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages In Rossi, F, Van Beek, P, Walsh, T (Eds.), Handbook of Constraint Programming, Foundations of Artificial Intelligence (Vol. 2, pp. 245–280). New York: Elsevier. doi:10.1016/S1574-6526(06)80012-X.
Cohen, D., Jeavons, P., Gyssens, M. (2008). A unified theory of structural tractability for constraint satisfaction problems. Journal of Computer and System Sciences, 74(5), 721–743. doi:10.1016/j.jcss.2007.08.001. http://www.sciencedirect.com/science/article/pii/S0022000007001225.
Cohen, D.A., Green, M.J., Houghton, C. (2009). Constraint representations and structural tractability. In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP’09), Lecture Notes in Computer Science, (Vol. 5732. pp. 289–303). Berlin: Springer.
Cohen, D.A., Jeavons, P.G., Thorstensen, E., živný, S. (2013). Tractable combinations of global constraints In Schulte, C (Ed.), Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP’13), Lecture Notes in Computer Science (Vol. 8124, pp. 230–246). Berlin: Springer.
Dalmau, V., Kolaitis, P.G., Vardi, M.Y. (2002). Constraint satisfaction, bounded treewidth, and finite-variable logics. In Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming (CP’02), Lecture Notes in Computer Science, (Vol. 2470. pp. 223–254). Berlin: Springer. http://dl.acm.org/citation.cfm?id=647489.727145.
Downey, R.G., & Fellows, M.R. (1999). Parameterized complexity. Monographs in computer science. Berlin: Springer.
Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Texts in theoretical computer science. Berlin: Springer.
Garey, M.R., & Johnson, D.S. (1979). Computers and intractability: A guide to the theory of NP-Completeness. San Francisco: W. H. Freeman.
Gaspers, S., & Szeider, S. (2012). Backdoors to satisfaction In Bodlaender, HL, Downey, R, Fomin, FV, Marx, D (Eds.), The multivariate algorithmic revolution and beyond, Lecture Notes in Computer Science (Vol. 7370, pp. 287–317). Berlin: Springer. doi:10.1007/978-3-642-30891-8_15.
Gent, I.P., Jefferson, C., Miguel, I. (2006). MINION: A fast, scalable constraint solver. In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI’06). (pp. 98–102). Amsterdam: IOS Press. http://dl.acm.org/citation.cfm?id= 1567016.1567043.
de Givry, S., Schiex, T., Verfaillie, G. (2006). Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP. In Proceedings of the 21st National Conference on Artificial Intelligence (AAAI’06). (pp. 22–27).
Gottlob, G., Greco, G., Scarcello, F. (2009). Tractable optimization problems through hypergraph-based structural restrictions In Albers, S, Marchetti-Spaccamela, A, Matias, Y, Nikoletseas, S, Thomas, W (Eds.), Proceedings of the 36th International Colloquium on Automata Languages and Programming (ICALP’09), Lecture Notes in Computer Science, (Vol. 5556, pp. 16–30). Berlin: Springer. doi:10.1007/978-3-642-02930-1_2.
Gottlob, G., Leone, N., Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2), 243–282.
Gottlob, G., Leone, N., Scarcello, F. (2002). Hypertree decompositions and tractable queries. Journal of Computer and System Sciences, 64(3), 579–627. doi:10.1006/jcss.2001.1809.
Green, M.J., & Jefferson, C. (2008). Structural tractability of propagated constraints. In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP’08), Lecture Notes in Computer Science, (Vol. 5202. pp. 372–386). Berlin: Springer. doi:10.1007/978-3-540-85958-1_25.
Grohe, M. (2007). The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1), 1–24. doi:10.1145/1206035.1206036.
Grohe, M., & Marx, D. (2006). Constraint solving via fractional edge covers. In Proceedings of the 17th ACM-SIAM symposium on discrete algorithms (SODA’06). (pp. 289–298): ACM. doi:10.1145/1109557.1109590.
Hermenier, F., Demassey, S., Lorca, X. (2011). Bin repacking scheduling in virtualized datacenters. In Lee, J (Ed.) Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming (CP’11), Lecture Notes in Computer Science, (Vol. 6876. pp. 27–41). Berlin: Springer. doi:10.1007/978-3-642-23786-7_5.
van Hoeve, W.J., & Katriel, I. (2006). Global constraints. In Rossi, F, Van Beek, P, Walsh, T (Eds.) Handbook of Constraint Programming, Foundations of Artificial Intelligence, (Vol. 2 . pp. 169–208). New York: Elsevier. doi:10.1016/S1574-6526(06)80010-6, http://www.sciencedirect.com/science/article/B8G6H-4RXCSGY-9/2/4e2eda11a2a06f3925df0334d09f0e1b.
Kutz, M., Elbassioni, K., Katriel, I., Mahajan, M. (2008). Simultaneous matchings: Hardness and approximation. Journal of Computer and System Sciences, 74(5), 884–897. doi:10.1016/j.jcss.2008.02.001. http://portal.acm.org/citation.cfm?id=1374847.1374923.
Marx, D. (2010). Approximating fractional hypertree width. ACM Transactions on Algorithms, 6(2), 29:1–29:17. doi:10.1145/1721837.1721845.
Marx, D. (2010). Can you beat treewidth Theory of Computing, 6(1), 85–112.
Marx, D. (2013). Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal ACM, 60(6), 42.
Quimper, C.G., López-Ortiz, A., van Beek, P., Golynski, A. (2004). Improved algorithms for the global cardinality constraint. In Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming (CP’04), Lecture Notes in Computer Science. (Vol. 3258, pp. 542–556). Berlin: Springer. doi:10.1007/978-3-540-30201-8_40.
Régin, J.C. (1996). Generalized Arc Consistency for Global Cardinality Constraint. In Proceedings of the 13th National Conference on Artificial Intelligence (AAAI’96). (pp. 209–215): AAAI Press . http://www.aaai.org/Papers/AAAI/1996/AAAI96-031. pdf.
Rossi, F., van Beek, P., Walsh, T. (2006). The handbook of constraint programming. New York: Elsevier.
Samer, M., & Szeider, S. (2011). Tractable cases of the extended global cardinality constraint. Constraints, 16(1), 1–24. doi:10.1007/s10601-009-9079-y.
Schiex, T., Fargier, H., Verfaillie, G. (1995). Valued Constraint Satisfaction Problems: Hard and Easy Problems In Mellish, C (Ed.), Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI’95), (pp. 631–639).
Wallace, M. (1996). Practical applications of constraint programming. Constraints, 1, 139–168.
Wallace, M., Novello, S., Schimpf, J. (1997). ECLiPSe: A platform for constraint logic programming. ICL Systems Journal, 12(1), 137–158.
Williams, R., Gomes, C.P., Selman, B. (2003). Backdoors to typical case complexity. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI’03). (pp. 1173–1178).
żivný, S. (2009). The complexity and expressive power of valued constraints. Doctoral dissertation: University of Oxford.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper appeared in Proceedings of the 19th International Conference on Principles and Practice of Constraint Programming (CP 2013).
Rights and permissions
About this article
Cite this article
Thorstensen, E. Structural decompositions for problems with global constraints. Constraints 21, 198–222 (2016). https://doi.org/10.1007/s10601-015-9181-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-015-9181-2