article

Tractability in constraint satisfaction problems: a survey

Authors:

Clément Carbonnel,

Martin C. CooperAuthors Info & Claims

Constraints, Volume 21, Issue 2

Pages 115 - 144

https://doi.org/10.1007/s10601-015-9198-6

Published: 01 April 2016 Publication History

Abstract

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.

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.

[2]

Adler, I., Gottlob, G., & Grohe, M. (2007). Hypertree width and related hypergraph invariants. European Journal of Combinatorics, 28(8), 2167---2181.

Digital Library

[3]

Allen, J.F. (1983). Maintaining knowledge about temporal intervals. Communications of the ACM, 26, 832---843.

Digital Library

[4]

Arnborg, S. (1985). Efficient algorithms for combinatorial problems with bounded decomposability - a survey. BIT, 25(1), 2---23.

Digital Library

[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.

Digital Library

[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.

[8]

Barto, L. (2015). The collapse of the bounded width hierarchy. Journal of Logic and Computation.

[9]

Barto, L., & Kozik, M. (2014). Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM, 61(1), 3.

Digital Library

[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.

Digital Library

[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.

Digital Library

[12]

van Beek, P., & Dechter, R. (1997). Constraint tightness and looseness versus local and global consistency. Journal of the ACM, 44(4), 549---566.

Digital Library

[13]

Bertelè, U., & Brioshi, F. (1972). Nonserial dynamic programming. Academic Press.

[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.

[16]

Bodirsky, M., & Chen, H. (2009). Relatively quantified constraint satisfaction. Constraints, 14(1), 3---15.

Digital Library

[17]

Bodirsky, M., Chen, H., Kára, J., & von Oertzen, T. (2009). Maximal infinite-valued constraint languages. Theoretical Computer Science, 410(18), 1684---1693.

Digital Library

[18]

Bodirsky, M., & Grohe, M. (2008). Non-dichotomies in constraint satisfaction complexity. In ICALP (pp. 184---196).

[19]

Bodirsky, M., & Kára, J. (2008). The complexity of equality constraint languages. Theory Computing Systems, 43(2), 136---158.

[20]

Bodirsky, M., & Kára, J. (2010). The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2), 9:1---9:41.

Digital Library

[21]

Bodlaender, H.L. (1996). A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6), 1305---1317.

Digital Library

[22]

Bulatov, A.A. (2006). Combinatorial problems raised from 2-semilattices. Journal of Algebra, 298(2), 321---339.

[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.

Digital Library

[24]

Bulatov, A.A. (2010). Bounded relational width. Tech. rep., School of Computer Science, Simon Fraser University.

[25]

Bulatov, A.A. (2011). Complexity of conservative constraint satisfaction problems. ACM Transactions on Computational Logic, 12(4), 24.

Digital Library

[26]

Bulatov, A.A. (2013). The complexity of the counting constraint satisfaction problem. Journal of the ACM, 60(5), 34.

Digital Library

[27]

Bulatov, A.A. (2014). Conservative constraint satisfaction re-revisited. preprint arXiv:1408.3690.

[28]

Bulatov, A.A., & Dalmau, V. (2006). A simple algorithm for Mal'tsev constraints. SIAM Journal on Computing, 36(1), 16---27.

Digital Library

[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.

[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.

[31]

Bulatov, A.A., & Jeavons, P.G. (2001). Algebraic structures in combinatorial problems. Tech. Rep. MATH-AL-4-2001, Technische Universität Dresden.

[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.

Digital Library

[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.

[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.

[35]

Bulatov, A.A., & Marx, D. (2014). Constraint satisfaction parameterized by solution size. SIAM Journal on Computing, 43(2), 573---616.

[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.

[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.

[38]

Carvalho, C., Egri, L., Jackson, M., & Niven, T. (2011). On Maltsev digraphs. In Computer Science---Theory and Applications (pp. 181---194). Springer.

[39]

Chen, H. (2009). A rendezvous of logic, complexity, and algebra. ACM Computing Surveys, 42(1).

[40]

Chen, H., Dalmau, V., & Grußien, B. (2013). Arc consistency and friends. Journal of Logic and Computation, 23(1), 87---108.

Digital Library

[41]

Chen, H., & Grohe, M. (2010). Constraint satisfaction with succinctly specified relations. Journal of Computer and System Sciences, 76(8), 847---860.

Digital Library

[42]

Chen, J., Kanj, I.A., & Xia, G. (2010). Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40), 3736---3756.

Digital Library

[43]

Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., & Vuskovic, K. (2005). Recognizing Berge graphs. Combinatorica, 25(2), 143---186.

Digital Library

[44]

Chudnovsky, M., Robertson, N., Seymour, P., & Thomas, R. (2006). The strong perfect graph theorem. Annals of Math, 164(1), 51---229.

[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.

[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.

[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.

Digital Library

[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.

[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.

[50]

Cohen, D.A., Jeavons, P., Jonsson, P., & Koubarakis, M. (2000). Building tractable disjunctive constraints. Journal of the ACM, 47(5), 826---853.

Digital Library

[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.

[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.

Digital Library

[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.

Digital Library

[56]

Cooper, M.C., & Escamocher, G. (2012). A dichotomy for 2-constraint forbidden CSP patterns. In J. Hoffmann, & B. Selman (Eds.), AAAI. AAAI Press.

[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.

[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.

[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.

Digital Library

[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.

[61]

Cooper, M.C., & ¿ivný, S. (2011). Hybrid tractability of valued constraint problems. Artificial Intelligence, 175(9-10), 1555---1569.

Digital Library

[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.

Digital Library

[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).

Digital Library

[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.

[65]

Creignou, N., Kolaitis, P., & Vollmer, H. (Eds.) (2008). Complexity of Constraints, Lecture Notes in Computer Science, Vol. 5250. Springer.

[66]

Dalmau, V. (2000). A new tractable class of constraint satisfaction problems, AMAI.

[67]

Dalmau, V. (2006). Generalized majority-minority operations are tractable. Logical Methods in Computer Science, 2(4), 438---447.

[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.

[69]

David, P. (1995). Using pivot consistency to decompose and solve functional CSPs. Journal of Artificial Intelligence Research (JAIR), 2, 447---474.

[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.

Digital Library

[72]

Dechter, R. (1992). From local to global consistency. Artificial Intelligence, 55 (1), 87---108.

Digital Library

[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.

Digital Library

[75]

Dechter, R., & Pearl, J. (1987). Network-based heuristics for constraint-satisfaction problems. Artificial Intelligence, 34(1), 1---38.

Digital Library

[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.

[77]

Deville, Y., Barette, O., & Hentenryck, P.V. (1999). Constraint satisfaction over connected row convex constraints. Artificial Intelligence, 109(1-2), 243---271.

Digital Library

[78]

Downey, R.G., & Fellows, M.R. (1995). Fixed-parameter tractability and completeness I: Basic results. SIAM Journal on Computing, 24(4), 873---921.

Digital Library

[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.

[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.

[82]

Dyer, M.E., Goldberg, L.A., & Jerrum, M. (2009). The complexity of weighted boolean #CSP. SIAM Journal on Computing, 38(5), 1970---1986.

Digital Library

[83]

Edmonds, J. (1965). Paths, trees and flowers. Canadian Journal of Mathematics, 17, 449---467.

[84]

Feder, T., & Hell, P. (2006). Full constraint satisfaction problems. SIAM Journal on Computing, 36(1), 230---246.

Digital Library

[85]

Feder, T., & Kolaitis, P.G. (2006). Closures and dichotomies for quantified constraints. Electronic Colloquium on Computational Complexity (ECCC), 13(160).

[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.

Digital Library

[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.

[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.

[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.

[92]

Gerevini, A., & Cristani, M. (1997). On finding a solution in temporal constraint satisfaction problems. In IJCAI (pp. 1460---1465).

[93]

Gottlob, G., Leone, N., & Scarcello, F. (2002). Hypertree decomposition and tractable queries. Journal of Computer and System Sciences, 64(3), 579---627.

Digital Library

[94]

Green, M.J., & Cohen, D.A. (2008). Domain permutation reduction for constraint satisfaction problems. Artificial Intelligence, 172(8-9), 1094---1118.

Digital Library

[95]

Grohe, M. (2001). Generalized model-checking problems for first-order logic. In STACS 2001 (pp. 12---26). Springer.

[96]

Grohe, M. (2006). The structure of tractable constraint satisfaction problems. In MFCS (pp. 58---72).

[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.

Digital Library

[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.

[99]

Grohe, M. (2014). Marx, D.: Constraint solving via fractional edge covers. ACM Transactions on Algorithms, 11(1), 4.

Digital Library

[100]

Grötschel, M., Lovasz, L., & Schrijver, A. (1981). The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1, 169---198.

[101]

Hell, P., & Nešetril, J. (1990). On the complexity of h-coloring. Journal of Combinatorial Theory, Series B, 48(1), 92---110.

Digital Library

[102]

Hell, P., & Nešetril, J. (2008). Colouring, constraint satisfaction, and complexity. Computer Science Review, 2(3), 143---163.

Digital Library

[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.

[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.

Digital Library

[105]

Iwata, S., & Orlin, J.B. (2009). A simple combinatorial algorithm for submodular function minimization. In SODA (pp. 1230---1237).

[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.

Digital Library

[108]

Jeavons, P., & Petke, J. (2012). Local consistency and SAT-solvers. Journal of Artificial Intelligence Research (JAIR), 43, 329---351.

Digital Library

[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.

Digital Library

[111]

Jeavons, P.G., Cohen, D.A., & Cooper, M.C. (1998). Constraints, consistency and closure. Artificial Intelligence, 101(1---2), 251---265.

[112]

Jeavons, P.G., & Cooper, M.C. (1995). Tractable constraints on ordered domains. Artificial Intelligence, 79(2), 327---339.

Digital Library

[113]

Jeavons, P.G., Krokhin, A.A., & ¿ivný, S. (2014). The complexity of valued constraint satisfaction: Bulletin of EATCS.

[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.

[115]

Jonsson, P., & Bäckström, C. (1998). A unifying approach to temporal constraint reasoning. Artificial Intelligence, 102(1), 143---155.

Digital Library

[116]

Jonsson, P., & Drakengren, T. (1997). A complete classification of tractability in RCC-5. Journal of Artificial Intelligence Research, 6, 211---221.

Digital Library

[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.

[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.

[119]

Kazda, A. (2011). CSP for binary conservative relational structures. preprint arXiv:1112.1099.

[120]

Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015). The complexity of general-valued CSPs. arXiv preprint arXiv:1502.07327.

[121]

Kolmogorov, V., & ¿ivný, S. (2013). The complexity of conservative valued CSPs. Journal of the ACM, 60(2), 10.

[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.

[123]

Kozik, M. (2008). A finite set of functions with an EXPTIME-complete composition problem. Theoretical Computer Science, 407(1---3), 330---341.

[124]

Kozik, M., Krokhin, A., Valeriote, M., & Willard, R. Characterizations of several Maltsev conditions. preprint (2013). (to appear in Algebra Universalis).

[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.

Digital Library

[126]

Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453---477.

Digital Library

[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.

[128]

Ladner, R.E. (1975). On the structure of polynomial time reducibility. Journal of the ACM, 22(1), 155---171.

Digital Library

[129]

Larose, B., Loten, C., & Tardif, C. (2007). A characterisation of first-order constraint satisfaction problems. preprint arXiv:0707.2562.

[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.

[131]

Lesaint, D., Azarmi, N., Laithwaite, R., & Walker, P. (1998). Engineering dynamic scheduler for Work Manager. BT Technology Journal, 16, 16---29.

Digital Library

[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).

[133]

Luczak, T., & Nesetril, J. (2006). A probabilistic approach to the dichotomy problem. SIAM Journal on Computing, 36(3), 835---843.

Digital Library

[134]

Marx, D. (2005). Parameterized complexity of constraint satisfaction problems. Computational Complexity, 14(2), 153---183.

Digital Library

[135]

Marx, D. (2010). Approximating fractional hypertree width. ACM Transactions on Algorithms, 6(2), 29:1---29:17.

[136]

Marx, D. (2011). Tractable structures for constraint satisfaction with truth tables. Theory Computing System, 48(3), 444---464.

Digital Library

[137]

Marx, D. (2013). Tractable hypergraph properties for constraint satisfaction and conjunctive queries. Journal of the ACM, 60(6), 42.

Digital Library

[138]

Mouelhi, A.E., Jégou, P., & Terrioux, C. (2014). Different classes of graphs to represent microstructures for CSPs (Vol. 8323, pp. 21---38).

[139]

Naanaa, W. (2013). Unifying and extending hybrid tractable classes of CSPs. Journal of Experimental & Theoretical Artificial Intelligence, 25(4), 407---424.

[140]

Ordyniak, S., Paulusma, D., & Szeider, S. (2013). Satisfiability of acyclic and almost acyclic CNF formulas. Theoretical Computer Science, 481, 85---99.

Digital Library

[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.

[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.

[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.

[144]

Pralet, C., & Verfaillie, G. (2012). Time-dependent simple temporal networks. In CP (pp. 608---623).

[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.

Digital Library

[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.

Digital Library

[149]

Schaefer, T.J. (1978). The complexity of satisfiability problems. In Proceedings 10th ACM Symposium on Theory of Computing, STOC'78 (pp. 216---226).

[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.

[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.

Digital Library

[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.

[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.

[154]

Welsh, D. (1993). Complexity: Knots, Colourings and Counting. Cambridge University Press.

[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.

Digital Library

[156]

Willard, R. (2010). Testing expressibility is hard. In D. Cohen (Ed.), CP, Lecture Notes in Computer Science, (Vol. 6308 pp. 9---23). Springer.

[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.

[158]

Yorke-Smith, N., & Gervet, C. (2009). Certainty closure: Reliable constraint reasoning with incomplete or erroneous data. ACM Transactions on Computational Logic, 10(1).

[159]

¿ivný, S. (2012). The complexity of valued constraint satisfaction problems. Cognitive technologies. Springer.

[160]

Zytnicki, M., Gaspin, C., & Schiex, T. (2008). DARN! A weighted constraint solver for RNA motif localization. Constraints, 13(1---2), 91---109.

Cited By

Dreier JOrdyniak SSzeider S(2023)CSP beyond tractable constraint languagesConstraints10.1007/s10601-023-09362-328:3(450-471)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1007/s10601-023-09362-3
Kratsch SMasařík TMuzi IPilipczuk MSorge MMarx D(2021)Optimal discretization is fixed-parameter tractableProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458167(1702-1719)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458167
Jonsson PLagerkvist VRoy B(2021)Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory10.1145/343438713:1(1-32)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434387
Show More Cited By

Index Terms

Tractability in constraint satisfaction problems: a survey
1. Theory of computation
  1. Design and analysis of algorithms
  2. Logic
    1. Constraint and logic programming

Recommendations

Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many ...
A Dichotomy for Real Weighted Holant Problems

Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as the counting constraint satisfaction problem (#CSP) and graph homomorphism. An effective dichotomy for such frameworks ...
Constraint satisfaction tractability from semi-lattice operations on infinite sets

A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Constraints

Constraints Volume 21, Issue 2

April 2016

240 pages

ISSN:1383-7133

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 April 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dreier JOrdyniak SSzeider S(2023)CSP beyond tractable constraint languagesConstraints10.1007/s10601-023-09362-328:3(450-471)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1007/s10601-023-09362-3
Kratsch SMasařík TMuzi IPilipczuk MSorge MMarx D(2021)Optimal discretization is fixed-parameter tractableProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458167(1702-1719)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458167
Jonsson PLagerkvist VRoy B(2021)Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory10.1145/343438713:1(1-32)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434387
Cohen DCooper MJeavons PŽivný S(2020)Galois Connections for Patterns: An Algebra of Labelled GraphsGraph Structures for Knowledge Representation and Reasoning10.1007/978-3-030-72308-8_9(125-150)Online publication date: 5-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-72308-8_9
Petrenko AAvellaneda FGroz ROriat C(2019)FSM inference and checking sequence construction are two sides of the same coinSoftware Quality Journal10.1007/s11219-018-9429-327:2(651-674)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s11219-018-9429-3
Jguirim WNaanaa WCooper M(2018)A polynomial relational class of binary CSPAnnals of Mathematics and Artificial Intelligence10.1007/s10472-017-9566-683:1(1-20)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10472-017-9566-6
Gaspers SMisra NOrdyniak SSzeider Sźivný S(2017)Backdoors into heterogeneous classes of SAT and CSPJournal of Computer and System Sciences10.1016/j.jcss.2016.10.00785:C(38-56)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jcss.2016.10.007
Cooper MŽivný SKoskinen EGrohe MShankar N(2016)The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden PatternsProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2933587(652-661)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2933575.2933587

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents