×

Tractability in constraint satisfaction problems: a survey. (English) Zbl 1334.90220

Summary: Even though the Constraint Satisfaction Problem (CSP) is NP-complete, many tractable classes of CSP instances have been identified. After discussing different forms and uses of tractability, we describe some landmark tractable classes and survey recent theoretical results. Although we concentrate on the classical CSP, we also cover its important extensions to infinite domains and optimisation, as well as #CSP and QCSP.

MSC:

90C60 Abstract computational complexity for mathematical programming problems
90C30 Nonlinear programming

Software:

DARN!; ToulBar2
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abrahamson, K.A., Downey, R.G., & Fellows, M.R. (1995). Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic, 73(3), 235-276. · Zbl 0828.68077 · doi:10.1016/0168-0072(94)00034-Z
[2] Adler, I., Gottlob, G., & Grohe, M. (2007). Hypertree width and related hypergraph invariants. European Journal of Combinatorics, 28(8), 2167-2181. · Zbl 1127.05065 · doi:10.1016/j.ejc.2007.04.013
[3] Allen, J.F. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM, 26, 832-843. · Zbl 0519.68079 · doi:10.1145/182.358434
[4] Arnborg, S. (1985). Efficient algorithms for combinatorial problems with bounded decomposability - a survey. BIT, 25(1), 2-23. · Zbl 0573.68018 · doi:10.1007/BF01934985
[5] Arnborg, S., Corneil, D.G., & Proskurowski, A. (1987). Complexity of finding an embedding in k-trees. SIAM journal of Algebraic and Discrete Methods, 8, 277-284. · Zbl 0611.05022 · doi:10.1137/0608024
[6] Barto, L. (2011). The dichotomy for conservative constraint satisfaction problems revisited. In LICS (pp. 301-310): IEEE Computer Society.
[7] Barto, L. (2011). Finitely related algebras in congruence distributive varieties have near unanimity terms. Canadian Journal of Mathematics. · Zbl 1283.08009
[8] Barto, L. (2015). The collapse of the bounded width hierarchy. Journal of Logic and Computation. doi:10.1093/logcom/exu070. · Zbl 1353.68107 · doi:10.1093/logcom/exu070
[9] Barto, L., & Kozik, M. (2014). Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM, 61(1), 3. · Zbl 1295.68126 · doi:10.1145/2556646
[10] Barto, L., Kozik, M., & Niven, T. (2009). The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of bang-jensen and hell). SIAM Journal on Computing, 38(5), 1782-1802. · Zbl 1191.68460 · doi:10.1137/070708093
[11] van Beek, P., & Dechter, R. (1995). On the minimality and decomposability of row-convex constraint networks. Journal of the ACM, 42(3), 543-561. · Zbl 0885.68087 · doi:10.1145/210346.210347
[12] van Beek, P., & Dechter, R. (1997). Constraint tightness and looseness versus local and global consistency. Journal of the ACM, 44(4), 549-566. · Zbl 0890.68075 · doi:10.1145/263867.263499
[13] Bertelè, U., & Brioshi, F. (1972). Nonserial dynamic programming. Academic Press. · Zbl 0244.49007
[14] Bessière, C., Carbonnel, C., Hébrard, E., Katsirelos, G., & Walsh, T. (2013). Detecting and exploiting subproblem tractability. In Proceedings of the 23rd international joint conference on Artificial Intelligence (pp. 468-474). AAAI Press.
[15] Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., & Fargier, H. (1999). Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison. Constraints, 4, 199-240. · Zbl 0946.68143 · doi:10.1023/A:1026441215081
[16] Bodirsky, M., & Chen, H. (2009). Relatively quantified constraint satisfaction. Constraints, 14(1), 3-15. · Zbl 1191.68625 · doi:10.1007/s10601-008-9054-z
[17] Bodirsky, M., Chen, H., Kára, J., & von Oertzen, T. (2009). Maximal infinite-valued constraint languages. Theoretical Computer Science, 410(18), 1684-1693. · Zbl 1172.68052 · doi:10.1016/j.tcs.2008.12.050
[18] Bodirsky, M., & Grohe, M. (2008). Non-dichotomies in constraint satisfaction complexity. In ICALP (pp. 184-196). · Zbl 1155.68403
[19] Bodirsky, M., & Kára, J. (2008). The complexity of equality constraint languages. Theory Computing Systems, 43(2), 136-158. · Zbl 1148.68025 · doi:10.1007/s00224-007-9083-9
[20] Bodirsky, M., & Kára, J. (2010). The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2), 9:1-9:41. · Zbl 1327.68125 · doi:10.1145/1667053.1667058
[21] Bodlaender, H.L. (1996). A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6), 1305-1317. · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[22] Bulatov, A.A. (2006). Combinatorial problems raised from 2-semilattices. Journal of Algebra, 298(2), 321-339. · Zbl 1110.08001 · doi:10.1016/j.jalgebra.2004.07.044
[23] Bulatov, A.A. (2006). A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM, 53(1), 66-120. · Zbl 1316.68057 · doi:10.1145/1120582.1120584
[24] Bulatov, A.A. (2010). Bounded relational width. Tech. rep., School of Computer Science, Simon Fraser University. · Zbl 1360.68499
[25] Bulatov, A.A. (2011). Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic, 12(4), 24. · Zbl 1351.68113 · doi:10.1145/1970398.1970400
[26] Bulatov, A.A. (2013). The complexity of the counting constraint satisfaction problem. Journal of the ACM, 60(5), 34. · Zbl 1281.68130
[27] Bulatov, A.A. (2014). Conservative constraint satisfaction re-revisited. preprint arXiv:1408.3690. · Zbl 1346.68108
[28] Bulatov, A.A., & Dalmau, V. (2006). A simple algorithm for Mal’tsev constraints. SIAM Journal on Computing, 36(1), 16-27. · Zbl 1112.08002 · doi:10.1137/050628957
[29] Bulatov, A.A., Dyer, M.E., Goldberg, L.A., Jalsenius, M., & Richerby, D. (2009). The complexity of weighted Boolean #CSP with mixed signs. Theoretical Computer Science, 410(38-40), 3949-3961. · Zbl 1171.68013 · doi:10.1016/j.tcs.2009.06.003
[30] Bulatov, A.A., Dyer, M.E., Goldberg, L.A., Jerrum, M., & McQuillan, C. (2013). The expressibility of functions on the boolean domain, with applications to counting CSPs. Journal of the ACM, 60(5), 32. · Zbl 1281.68131
[31] Bulatov, A.A., & Jeavons, P.G. (2001). Algebraic structures in combinatorial problems. Tech. Rep. MATH-AL-4-2001, Technische Universität Dresden. · Zbl 0912.68160
[32] Bulatov, A.A., Jeavons, P.G., & Krokhin, A.A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34, 720-742. · Zbl 1071.08002 · doi:10.1137/S0097539700376676
[33] Bulatov, A.A., Krokhin, A.A., & Jeavons, P. (2001). The complexity of maximal constraint languages. In J.S. Vitter, P.G. Spirakis, & M. Yannakakis (Eds.), STOC (pp. 667-674). ACM. · Zbl 1323.68294
[34] Bulatov, A.A., Krokhin, A.A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P.G. Kolaitis, & H. Vollmer (Eds.), Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar]., Lecture Notes in Computer Science, (Vol. 5250 pp. 93-124). Springer. · Zbl 1171.68494
[35] Bulatov, A.A., & Marx, D. (2014). Constraint satisfaction parameterized by solution size. SIAM Journal on Computing, 43(2), 573-616. · Zbl 1360.68499 · doi:10.1137/120882160
[36] Bulatov, A.A., Valeriote, M., P. Kolaitis, & H. Vollmer (2008). Recent results on the algebraic approach to the CSP. In N. Creignou (Ed.), Complexity of Constraints, Lecture Notes in Computer Science, (Vol. 5250 pp. 68-92). Berlin / Heidelberg: Springer. · Zbl 1171.08300
[37] Carbonnel, C., Cooper, M.C., & Hebrard, E. (2014). On backdoors to tractable constraint languages. In B. O’Sullivan (Ed.), Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings, Lecture Notes in Computer Science, (Vol. 8656 pp. 224-239). Springer. · Zbl 0890.68064
[38] Carvalho, C., Egri, L., Jackson, M., & Niven, T. (2011). On Maltsev digraphs. In Computer Science-Theory and Applications (pp. 181-194). Springer. · Zbl 1332.68068
[39] Chen, H. (2009). A rendezvous of logic, complexity, and algebra. ACM Computing Surveys, 42(1). · Zbl 1305.08007
[40] Chen, H., Dalmau, V., & Grußien, B. (2013). Arc consistency and friends. Journal of Logic and Computation, 23(1), 87-108. · Zbl 1282.68134 · doi:10.1093/logcom/exr039
[41] Chen, H., & Grohe, M. (2010). Constraint satisfaction with succinctly specified relations. Journal of Computer and System Sciences, 76(8), 847-860. · Zbl 1214.68347 · doi:10.1016/j.jcss.2010.04.003
[42] Chen, J., Kanj, I.A., & Xia, G. (2010). Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40), 3736-3756. · Zbl 1205.05217 · doi:10.1016/j.tcs.2010.06.026
[43] Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., & Vuskovic, K. (2005). Recognizing Berge graphs. Combinatorica, 25(2), 143-186. · Zbl 1089.05027 · doi:10.1007/s00493-005-0012-8
[44] Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (2006). The strong perfect graph theorem. Annals of Math, 164(1), 51-229. · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51
[45] Cobham, A. (1964). The intrinsic computational difficulty of functions. In Proceedings of International Congress for Logic, Methodology, and Philosophy of Science (pp. 24-30). North-Holland. · Zbl 0492.90056
[46] Cohen, D.A., Cooper, M.C., Creed, P., Jeavons, P.G., & živný, S. (2013). An algebraic theory of complexity for discrete optimisation. SIAM Journal on Computing, 42(5), 1915-1939. · Zbl 1305.08007 · doi:10.1137/130906398
[47] Cohen, D.A., Cooper, M.C., Creed, P., Marx, D., & Salamon, A.Z. (2012). The tractability of CSP classes defined by forbidden patterns. Journal of Artificial Intelligence Research (JAIR), 45, 47-78. · Zbl 1253.68296
[48] Cohen, D.A., Cooper, M.C., Green, M.J., & Marx, D. (2011). On guaranteeing polynomially bounded search tree size. In J.H.M. Lee (Ed.), CP, Lecture Notes in Computer Science, (Vol. 6876 pp. 160-171). Springer. · Zbl 1312.68101
[49] Cohen, D.A., Cooper, M.C., Jeavons, P., & Krokhin, A.A. (2006). The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11), 983-1016. · Zbl 1131.68520 · doi:10.1016/j.artint.2006.04.002
[50] Cohen, D.A., Jeavons, P., Jonsson, P., & Koubarakis, M. (2000). Building tractable disjunctive constraints. Journal of the ACM, 47(5), 826-853. · Zbl 1320.68169 · doi:10.1145/355483.355485
[51] Cohen, D.A., & Jeavons, P.G. (2006). The complexity of constraint languages. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of constraint programming (pp. 245-280). Elsevier. · Zbl 1052.68025
[52] Cook, S.A. (1971). The complexity of theorem-proving procedures. In M.A. Harrison, R.B. Banerji, & J.D. Ullman (Eds.), STOC (pp. 151-158). ACM.
[53] Cooper, M.C. (1999). Linear-time algorithms for testing the realisability of line drawings of curved objects. Artificial Intelligence, 108, 31-67. · Zbl 0914.68193 · doi:10.1016/S0004-3702(98)00118-0
[54] Cooper, M.C. (2014). Beyond consistency and substitutability. In CP (pp. 256-271).
[55] Cooper, M.C., Cohen, D.A., & Jeavons, P. (1994). Characterising tractable constraints. Artificial Intelligence, 65(2), 347-361. · Zbl 0803.68053 · doi:10.1016/0004-3702(94)90021-3
[56] Cooper, M.C., & Escamocher, G. (2012). A dichotomy for 2-constraint forbidden CSP patterns. In J. Hoffmann, & B. Selman (Eds.), AAAI. AAAI Press. · Zbl 0132.20903
[57] Cooper, M.C., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., & Werner, T. (2010). Soft arc consistency revisited. Artificial Intelligence, 174(7-8), 449-478. · Zbl 1213.68580 · doi:10.1016/j.artint.2010.02.001
[58] Cooper, M.C., Jeavons, P.G., & Salamon, A.Z. (2010). Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination. Artificial Intelligence, 174(9-10), 570-584. · Zbl 1205.68372 · doi:10.1016/j.artint.2010.03.002
[59] Cooper, M.C., Maris, F., & Régnier, P. (2014). Monotone temporal planning: Tractability, extensions and applications. Journal of Artificial Intelligence Research (JAIR), 50, 447-485. · Zbl 1372.68232
[60] Cooper, M.C., Mouelhi, A.E., Terrioux, C., & Zanuttini, B. (2014). On broken triangles. In O’Sullivan, B (Ed.), Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings, Lecture Notes in Computer Science, (Vol. 8656 pp. 9-24). Springer. · Zbl 0643.68156
[61] Cooper, M.C., & živný, S. (2011). Hybrid tractability of valued constraint problems. Artificial Intelligence, 175(9-10), 1555-1569. · Zbl 1225.68243 · doi:10.1016/j.artint.2011.02.003
[62] Cooper, M.C., & živný, S. (2012). Tractable triangles and cross-free convexity in discrete optimisation. Journal of Artificial Intelligence Research (JAIR), 44, 455-490. · Zbl 1254.90309
[63] Courcelle, B. (1990). Graph rewriting: An algebraic and logic approach. In Handbook of theoretical computer science, Volume B: formal models and sematics (B) (pp. 193-242). · Zbl 0900.68282
[64] Creignou, N., & Hébrard, J.J. (1997). On generating all solutions of generalized satisfiability problems. Informatique Théorique et Applications, 31(6), 499-511. · Zbl 0901.68075
[65] Creignou, N., Kolaitis, P., & Vollmer, H. (Eds.) (2008). Complexity of Constraints, Lecture Notes in Computer Science, Vol. 5250. Springer. · Zbl 1154.68008
[66] Dalmau, V. (2000). A new tractable class of constraint satisfaction problems, AMAI. · Zbl 1075.68082
[67] Dalmau, V. (2006). Generalized majority-minority operations are tractable. Logical Methods in Computer Science, 2(4), 438-447. · Zbl 1127.68039 · doi:10.2168/LMCS-2(4:1)2006
[68] Dalmau, V., & Pearson, J. (1999). Closure functions and width 1 problems. In Principles and Practice of Constraint Programming-CP 99 (pp. 159-173). Springer. · Zbl 0957.68081
[69] David, P. (1995). Using pivot consistency to decompose and solve functional CSPs. Journal of Artificial Intelligence Research (JAIR), 2, 447-474. · Zbl 0900.68299
[70] de Givry, S., Schiex, T., & Verfaillie, G. (2006). Exploiting tree decomposition and soft local consistency in weighted CSP. In AAAI (pp. 22-27).
[71] de Haan, R. Kanj (2015). On the subexponential-time complexity of CSP. Journal of Artificial Intelligence Research, 52, 203-234. · Zbl 1323.68325
[72] Dechter, R. (1992). From local to global consistency. Artificial Intelligence, 55 (1), 87-108. · Zbl 0762.68053 · doi:10.1016/0004-3702(92)90043-W
[73] Dechter, R. (2003). Constraint processing, (pp. 94104-3205). San Francisco: Morgan Kaufmann Publishers.
[74] Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial Intelligence, 49(1-3), 61-95. · Zbl 0737.68070 · doi:10.1016/0004-3702(91)90006-6
[75] Dechter, R., & Pearl, J. (1987). Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence, 34(1), 1-38. · Zbl 0643.68156 · doi:10.1016/0004-3702(87)90002-6
[76] Dehne, F.K.H.A., Fellows, M.R., Langston, M.A., Rosamond, F.A., & Stevens, K. (2005). An o(2o(k)n3) FPT algorithm for the undirected feedback vertex set problem. In L. Wang (Ed.), Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings, Lecture Notes in Computer Science, (Vol. 3595 pp. 859-869). Springer. · Zbl 1128.68400
[77] Deville, Y., Barette, O., & Hentenryck, P.V. (1999). Constraint satisfaction over connected row convex constraints. Artificial Intelligence, 109(1-2), 243-271. · Zbl 0916.68061 · doi:10.1016/S0004-3702(99)00012-0
[78] Downey, R.G., & Fellows, M.R. (1995). Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24(4), 873-921. · Zbl 0830.68063 · doi:10.1137/S0097539792228228
[79] Downey, R.G., Fellows, M.R., & Stege, U. (1999). Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary trends in discrete mathematics: From DIMACS and DIMATIA to the future, (Vol. 49 pp. 49-99). AMS-DIMACS Proceedings Series. · Zbl 0935.68046
[80] Drakengren, T., & Jonsson, P. (2005). Computational complexity of temporal constraint problems. In M. Fisher, D. Gabbay, & L. Vila (Eds.), Handbook of temporal reasoning in artificial intelligence (pp. 197-218). Elsevier.
[81] Dyer, M., & Richerby, D. (2013). An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3), 1245-1274. · Zbl 1275.68077 · doi:10.1137/100811258
[82] Dyer, M.E., Goldberg, L.A., & Jerrum, M. (2009). The complexity of weighted boolean #CSP. SIAM Journal on Computing, 38(5), 1970-1986. · Zbl 1191.68351 · doi:10.1137/070690201
[83] Edmonds, J. (1965). Paths, trees and flowers. Canadian Journal of Mathematics, 17, 449-467. · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4
[84] Feder, T., & Hell, P. (2006). Full constraint satisfaction problems. SIAM Journal on Computing, 36(1), 230-246. · Zbl 1111.68115 · doi:10.1137/S0097539703427197
[85] Feder, T., & Kolaitis, P.G. (2006). Closures and dichotomies for quantified constraints. Electronic Colloquium on Computational Complexity (ECCC), 13(160). · Zbl 0894.68096
[86] Feder, T., & Vardi, M.Y. (1998). The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing, 28(1), 57-104. · Zbl 0914.68075 · doi:10.1137/S0097539794266766
[87] Freuder, E.C. (1990). Complexity of k-tree structured constraint satisfaction problems. In H.E. Shrobe, T.G. Dietterich, & W.R. Swartout (Eds.), AAAI (pp. 4-9). AAAI Press / The MIT Press.
[88] Gao, J., Yin, M., & Zhou, J. (2011). Hybrid tractable classes of binary quantified constraint satisfaction problems. In W. Burgard, & D. Roth (Eds.), AAAI. AAAI Press. · Zbl 1305.08007
[89] Gao, Y. (2003). Phase transition of tractability in constraint satisfaction and bayesian network inference. In UAI (pp. 265-271).
[90] Garey, M., & Johnson, D. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: W.H.Freeman and Company. · Zbl 0411.68039
[91] Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., & Zivny, S. (2014). Backdoors into heterogeneous classes of SAT and CSP. In C.E. Brodley, & P. Stone (Eds.), Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27 -31, 2014, Québec City, Québec, Canada (pp. 2652-2658). AAAI Press. http://www.aaai.org/Library/AAAI/aaai14contents.php. · Zbl 1356.68097
[92] Gerevini, A., & Cristani, M. (1997). On finding a solution in temporal constraint satisfaction problems. In IJCAI (pp. 1460-1465). · Zbl 1282.68134
[93] Gottlob, G., Leone, N., & Scarcello, F. (2002). Hypertree decomposition and tractable queries. Journal of Computer and System Sciences, 64(3), 579-627. · Zbl 1052.68025 · doi:10.1006/jcss.2001.1809
[94] Green, M.J., & Cohen, D.A. (2008). Domain permutation reduction for constraint satisfaction problems. Artificial Intelligence, 172(8-9), 1094-1118. · Zbl 1183.68309 · doi:10.1016/j.artint.2007.12.001
[95] Grohe, M. (2001). Generalized model-checking problems for first-order logic. In STACS 2001 (pp. 12-26). Springer. · Zbl 0976.68077
[96] Grohe, M. (2006). The structure of tractable constraint satisfaction problems. In MFCS (pp. 58-72). · Zbl 1132.68700
[97] Grohe, M. (2007). The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM, 54(1), 1-24. · Zbl 1312.68101 · doi:10.1145/1206035.1206036
[98] Grohe, M., Kreutzer, S., & Siebertz, S. (2014). Deciding first-order properties of nowhere dense graphs. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (pp. 89-98). ACM. · Zbl 1315.05118
[99] Grohe, M. (2014). Marx, D.: Constraint solving via fractional edge covers. ACM Transactions on Algorithms, 11(1), 4. · Zbl 1398.68240 · doi:10.1145/2636918
[100] Grötschel, M., Lovasz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169-198. · Zbl 0492.90056 · doi:10.1007/BF02579273
[101] Hell, P., & Nešetril, J. (1990). On the complexity of h-coloring. Journal of Combinatorial Theory, Series B, 48(1), 92-110. · Zbl 0639.05023 · doi:10.1016/0095-8956(90)90132-J
[102] Hell, P., & Nešetril, J. (2008). Colouring, constraint satisfaction, and complexity. Computer Science Review, 2(3), 143-163. · Zbl 1302.68251 · doi:10.1016/j.cosrev.2008.10.003
[103] Hermann, M., & Richoux, F. (2009). On the computational complexity of monotone constraint satisfaction problems. In S. Das, & R. Uehara (Eds.), WALCOM, Lecture Notes in Computer Science, (Vol. 5431 pp. 286-297). Springer. · Zbl 1211.68218
[104] Idziak, P.M., Markovic, P., McKenzie, R., Valeriote, M., & Willard, R. (2010). Tractability and learnability arising from algebras with few subpowers. SIAM Journal on Computing, 39(7), 3023-3037. · Zbl 1216.68129 · doi:10.1137/090775646
[105] Iwata, S., & Orlin, J.B. (2009). A simple combinatorial algorithm for submodular function minimization. In SODA (pp. 1230-1237). · Zbl 1423.90226
[106] Jeavons, P., Cohen, D., & Gyssens, M. (1995). A unifying framework for tractable constraints. In Proceedings 1st international conference on constraint programming, CP’95, (Vol. 976 pp. 276-291). Springer-Verlag.
[107] Jeavons, P., Cohen, D.A., & Gyssens, M. (1997). Closure properties of constraints. Journal of the ACM, 44(4), 527-548. · Zbl 0890.68064 · doi:10.1145/263867.263489
[108] Jeavons, P., & Petke, J. (2012). Local consistency and SAT-solvers. Journal of Artificial Intelligence Research (JAIR), 43, 329-351. · Zbl 1237.68187
[109] Jeavons, P.G. (1998). Constructing constraints. In Proceedings 4th International Conference on Constraint Programming—CP’98 (Pisa, October 1998), Lecture Notes in Computer Science, (Vol. 1520 pp. 2-16). Springer-Verlag.
[110] Jeavons, P.G. (1998). On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200, 185-204. · Zbl 0915.68074 · doi:10.1016/S0304-3975(97)00230-2
[111] Jeavons, P.G., Cohen, D.A., & Cooper, M.C. (1998). Constraints, consistency and closure. Artificial Intelligence, 101(1-2), 251-265. · Zbl 0909.68076 · doi:10.1016/S0004-3702(98)00022-8
[112] Jeavons, P.G., & Cooper, M.C. (1995). Tractable constraints on ordered domains. Artificial Intelligence, 79(2), 327-339. · Zbl 1013.68503 · doi:10.1016/0004-3702(95)00107-7
[113] Jeavons, P.G., Krokhin, A.A., & živný, S. (2014). The complexity of valued constraint satisfaction: Bulletin of EATCS. · Zbl 1087.68107
[114] Jégou, P. (1993). Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. In AAAI (pp. 731-736). Menlo Park: AAAI Press. · Zbl 1327.68125
[115] Jonsson, P., & Bäckström, C. (1998). A unifying approach to temporal constraint reasoning. Artificial Intelligence, 102(1), 143-155. · Zbl 0912.68160 · doi:10.1016/S0004-3702(98)00031-9
[116] Jonsson, P., & Drakengren, T. (1997). A complete classification of tractability in RCC-5. Journal of Artificial Intelligence Research, 6, 211-221. · Zbl 0894.68096
[117] Jonsson, P., Lagerkvist, V., Nordh, G., & Zanuttini, B. (2013). Complexity of SAT problems, clone theory and the exponential time hypothesis. In S. Khanna (Ed.), SODA (pp. 1264-1277). SIAM. · Zbl 1423.68212
[118] Karp, R.M. (1972). Reducibility among combinatorial problems. In R.E. Miller, & J.W. Thatcher (Eds.), Complexity of computer computations (pp. 85-103). Plenum Press. · Zbl 1467.68065
[119] Kazda, A. (2011). CSP for binary conservative relational structures. preprint arXiv:1112.1099. · Zbl 1356.08001
[120] Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015). The complexity of general-valued CSPs. arXiv preprint arXiv:1502.07327. · Zbl 1371.68117
[121] Kolmogorov, V., & živný, S. (2013). The complexity of conservative valued CSPs. Journal of the ACM, 60(2), 10. · Zbl 1281.68134 · doi:10.1145/2450142.2450146
[122] Koubarakis, M. (1996). Tractable disjunctions of linear constraints. In E.C. Freuder (Ed.), CP, Lecture Notes in Computer Science, (Vol. 1118 pp. 297-307). Springer. · Zbl 0885.68087
[123] Kozik, M. (2008). A finite set of functions with an EXPTIME-complete composition problem. Theoretical Computer Science, 407(1-3), 330-341. · Zbl 1152.68023 · doi:10.1016/j.tcs.2008.06.057
[124] Kozik, M., Krokhin, A., Valeriote, M., & Willard, R. Characterizations of several Maltsev conditions. preprint (2013). (to appear in Algebra Universalis). · Zbl 1319.08002
[125] Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra. Journal of the ACM, 50, 591-640. · Zbl 1325.68220 · doi:10.1145/876638.876639
[126] Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. · Zbl 1101.68043 · doi:10.1137/S0895480102410201
[127] Kun, G., & Szegedy, M. (2009). A new line of attack on the dichotomy conjecture. In M. Mitzenmacher (Ed.), Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 (pp. 725-734). ACM. · Zbl 1304.68076
[128] Ladner, R.E. (1975). On the structure of polynomial time reducibility. Journal of the ACM, 22(1), 155-171. · Zbl 0322.68028 · doi:10.1145/321864.321877
[129] Larose, B., Loten, C., & Tardif, C. (2007). A characterisation of first-order constraint satisfaction problems. preprint arXiv:0707.2562. · Zbl 1131.68098
[130] Larose, B., & Zádori, L. (2006). Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras. IJAC, 16(3), 563-582. · Zbl 1100.08004
[131] Lesaint, D., Azarmi, N., Laithwaite, R., & Walker, P. (1998). Engineering dynamic scheduler for Work Manager. BT Technology Journal, 16, 16-29. · doi:10.1023/A:1009609327253
[132] Lin, B. (2015). The parameterized complexity of k-biclique. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 (pp. 605-615). · Zbl 1371.68118
[133] Luczak, T., & Nesetril, J. (2006). A probabilistic approach to the dichotomy problem. SIAM Journal on Computing, 36(3), 835-843. · Zbl 1120.68059 · doi:10.1137/S0097539703435492
[134] Marx, D. (2005). Parameterized complexity of constraint satisfaction problems. Computational Complexity, 14(2), 153-183. · Zbl 1085.68068 · doi:10.1007/s00037-005-0195-9
[135] Marx, D. (2010). Approximating fractional hypertree width. ACM Transactions on Algorithms, 6(2), 29:1-29:17. · Zbl 1300.05201 · doi:10.1145/1721837.1721845
[136] Marx, D. (2011). Tractable structures for constraint satisfaction with truth tables. Theory Computing System, 48(3), 444-464. · Zbl 1253.68180 · doi:10.1007/s00224-009-9248-9
[137] Marx, D. (2013). Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM, 60(6), 42. · Zbl 1281.68135 · doi:10.1145/2535926
[138] Mouelhi, A.E., Jégou, P., & Terrioux, C. (2014). Different classes of graphs to represent microstructures for CSPs (Vol. 8323, pp. 21-38). · Zbl 1291.68182
[139] Naanaa, W. (2013). Unifying and extending hybrid tractable classes of CSPs. Journal of Experimental & Theoretical Artificial Intelligence, 25(4), 407-424. · doi:10.1080/0952813X.2012.721138
[140] Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85-99. doi:10.1016/j.tcs.2012.12.039. · Zbl 1291.68182 · doi:10.1016/j.tcs.2012.12.039
[141] Papadimitriou, C.H., & Yannakakis, M. (1997). On the complexity of database queries. In Proceedings of the 16th ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems (pp. 12-19). ACM. · Zbl 1111.68115
[142] Pearson, J.K., & Jeavons, P.G. (1997). A survey of tractable constraint satisfaction problems. Tech. Rep. CSD-TR-97-15, Royal Holloway, University of London. · Zbl 1186.68443
[143] Petke, J., & Jeavons, P. (2011). The order encoding: From tractable CSP to tractable SAT. In K.A. Sakallah, & L. Simon (Eds.), SAT, Lecture Notes in Computer Science, (Vol. 6695 pp. 371-372). Springer. · Zbl 0611.05022
[144] Pralet, C., & Verfaillie, G. (2012). Time-dependent simple temporal networks. In CP (pp. 608-623). · Zbl 1267.68218
[145] Purvis, L., & Jeavons, P. (1999). Constraint tractability theory and its application to the product development process for a constraint-based scheduler. In Proceedings of 1st International Conference on The Practical Application of Constraint Technologies and Logic Programming - PACLP’99 (pp. 63-79). Practical Applications Company.
[146] Robertson, N., & Seymour, P.D. (1995). Graph minors XIII. The disjoint paths problem. Journal of Combinatorial Theory Series B, 63(1), 65-110. · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006
[147] Salamon, A.Z., & Jeavons, P.G. (2008). Perfect constraints are tractable. In CP, Lecture Notes in Computer Science, (Vol. 5202 pp. 524-528): Springer.
[148] Samer, M., & Szeider, S. (2010). Constraint satisfaction with bounded treewidth revisited. Journal of Computer and System Sciences, 76(2), 103-114. · Zbl 1186.68443 · doi:10.1016/j.jcss.2009.04.003
[149] Schaefer, T.J. (1978). The complexity of satisfiability problems. In Proceedings 10th ACM Symposium on Theory of Computing, STOC’78 (pp. 216-226). · Zbl 1282.68143
[150] Scott, A.D., & Sorkin, G.B. (2009). Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Transactions on Algorithms, 5(4), 45:1-45:27. · Zbl 1298.68256 · doi:10.1145/1597036.1597049
[151] Thapper, J., & živný, S. (2012). The power of linear programming for valued CSPs. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012 (pp. 669-678). IEEE Computer Society.
[152] Thapper, J., & živný, S. (2013). The complexity of finite-valued CSPs. In D. Boneh, T. Roughgarden, & J. Feigenbaum (Eds.), STOC (pp. 695-704). ACM. · Zbl 1294.68094
[153] van Hoeve, W.J., & Katriel, I. (2006). Global constraints. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of Constraint Programming (chap. 6, pp. 169-208). Elsevier. · Zbl 1214.68347
[154] Welsh, D. (1993). Complexity: Knots, Colourings and Counting. Cambridge University Press. · Zbl 0799.68008
[155] Werner, T. (2007). A linear programming approach to max-sum problem: A review. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(7), 1165-1179. · doi:10.1109/TPAMI.2007.1036
[156] Willard, R. (2010). Testing expressibility is hard. In D. Cohen (Ed.), CP, Lecture Notes in Computer Science, (Vol. 6308 pp. 9-23). Springer. · Zbl 1205.05217
[157] Williams, R., Gomes, C.P., & Selman, B. (2003). Backdoors to typical case complexity. In G. Gottlob, & T. Walsh (Eds.), IJCAI (pp. 1173-1178). Morgan Kaufmann. · Zbl 1052.68025
[158] Yorke-Smith, N., & Gervet, C. (2009). Certainty closure: Reliable constraint reasoning with incomplete or erroneous data. ACM Transactions on Computational Logic, 10(1). · Zbl 1367.68272
[159] živný, S. (2012). The complexity of valued constraint satisfaction problems. Cognitive technologies. Springer. · Zbl 1283.68024
[160] Zytnicki, M., Gaspin, C., & Schiex, T. (2008). DARN! A weighted constraint solver for RNA motif localization. Constraints, 13(1-2), 91-109. · Zbl 1142.92015 · doi:10.1007/s10601-007-9033-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.