On singleton arc consistency for CSPs defined by monotone patterns. (English) Zbl 1421.68151

Summary: Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI


[1] Atserias, A., Bulatov, A., Dalmau, V.: On the power of k-consistency. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP’07), pp. 279-290 (2007). https://doi.org/10.1007/978-3-540-73420-8_26 · Zbl 1171.68720
[2] Barto, L.; Kozik, M., Constraint satisfaction problems solvable by local consistency methods, J. ACM, 61, 3, (2014) · Zbl 1295.68126
[3] Beldiceanu, N., Carlsson, M., Rampon, J.-X.: Global Constraint Catalog. http://sofdem.github.io/gccat/gccat/titlepage.html (2017)
[4] Berman, J.; Idziak, P.; Marković, P.; McKenzie, R.; Valeriote, M.; Willard, R., Varieties with few subalgebras of powers, Trans. Am. Math. Soc., 362, 1445-1473, (2010) · Zbl 1190.08004
[5] Bessiere, C.; Debruyne, R., Theoretical analysis of singleton arc consistency and its extensions, Artif. Intell., 172, 29-41, (2008) · Zbl 1182.68217
[6] Bessière, C.; Régin, J.; Yap, RHC; Zhang, Y., An optimal coarse-grained arc consistency algorithm, Artif. Intell., 165, 165-185, (2005) · Zbl 1132.68691
[7] Brailsford, SC; Potts, CN; Smith, BM, Constraint satisfaction problems: algorithms and applications, Eur. J. Oper. Res., 119, 557-581, (1999) · Zbl 0938.90055
[8] Bulatov, A.: Bounded relational width. Unpublished manuscript (2009). http://www.cs.sfu.ca/ abulatov/papers/relwidth.pdf
[9] Bulatov, A.; Dalmau, V., A simple algorithm for Mal’tsev constraints, SIAM J. Comput., 36, 16-27, (2006) · Zbl 1112.08002
[10] Bulatov, A.; Jeavons, P.; Krokhin, A., Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34, 720-742, (2005) · Zbl 1071.08002
[11] Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pp. 319-330 (2017). https://doi.org/10.1109/FOCS.2017.37
[12] Carbonnel, C., Cohen, D.A., Cooper, M.C., Živný, S.: On singleton arc consistency for CSPs defined by monotone patterns. In: Proceedings of the 35th Annual Symposium on Theoretical Aspects of Computer Science (STACS’18), pp. 19:1-19:15 (2018). https://doi.org/10.4230/LIPIcs.STACS.2018.19
[13] Chen, H.; Dalmau, V.; Gruien, B., Arc consistency and friends, J. Log. Comput., 23, 87, (2013) · Zbl 1282.68134
[14] Cheng, C-C; Smith, SF, Applying constraint satisfaction techniques to job shop scheduling, Ann. Oper. Res., 70, 327-357, (1997) · Zbl 0890.90093
[15] Cohen, DA; Cooper, MC; Escamocher, G.; Živný, S., Variable and value elimination in binary constraint satisfaction via forbidden patterns, J. Comput. Syst. Sci., 81, 1127-1143, (2015) · Zbl 1320.68168
[16] Cohen, DA; Jeavons, PG, The power of propagation: when GAC is enough, Constraints, 22, 3-23, (2017) · Zbl 1387.90130
[17] Cooper, MC; Cohen, DA; Creed, P.; Marx, D.; Salamon, AZ, The tractability of CSP classes defined by forbidden patterns, J. Artif. Intell. Res., 45, 47-78, (2012) · Zbl 1253.68296
[18] Cooper, MC; Cohen, DA; Jeavons, PG, Characterising tractable constraints, Artif. Intell., 65, 347-361, (1994) · Zbl 0803.68053
[19] Cooper, MC; Duchein, A.; Mouelhi, AE; Escamocher, G.; Terrioux, C.; Zanuttini, B., Broken triangles: from value merging to a tractable class of general-arity constraint satisfaction problems, Artif. Intell., 234, 196-218, (2016) · Zbl 1351.68253
[20] Cooper, MC; Escamocher, G., Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns, Discrete Appl. Math., 184, 89-113, (2015) · Zbl 1311.05004
[21] Cooper, MC; Jeavons, PG; Salamon, AZ, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Artif. Intell., 174, 570-584, (2010) · Zbl 1205.68372
[22] Cooper, MC; Živný, S., Hybrid tractability of valued constraint problems, Artif. Intell., 175, 1555-1569, (2011) · Zbl 1225.68243
[23] Cooper, M.C., Živný, S.: The power of arc consistency for CSPs defined by partially-ordered forbidden patterns. Log. Methods Comput. Sci. 13(4) (2017). https://doi.org/10.23638/LMCS-13(4:26)2017
[24] Freuder, EC, A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063
[25] Freuder, E.C.: Eliminating interchangeable values in constraint satisfaction problems. In: Proceedings of AAAI-91, pp. 227-233 (1991). http://www.aaai.org/Library/AAAI/1991/aaai91-036.php
[26] Grohe, M., The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1-24, (2007) · Zbl 1312.68101
[27] Idziak, P.; Marković, P.; McKenzie, R.; Valeriote, M.; Willard, R., Tractability and learnability arising from algebras with few subpowers, SIAM J. Comput., 39, 3023-3037, (2010) · Zbl 1216.68129
[28] Kozik, M.: Weak consistency notions for all the CSPs of bounded width. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’16), ACM, pp. 633-641 (2016). https://doi.org/10.1145/2933575.2934510 · Zbl 1401.68123
[29] Lim, N., Majumdar, S., Ashwood-Smith, P.: A constraint programming-based resource management technique for processing MapReduce jobs with SLSs on clouds. In: Proceedings of the 43rd International Conference on Parallel Processing (ICPP’14), IEEE, pp. 411-421 (2014). https://doi.org/10.1109/ICPP.2014.50
[30] Mohr, R.; Henderson, TC, Arc and path consistency revisited, Artif. Intell., 28, 225-233, (1986)
[31] Ozturk, C.; Ornek, MA, Optimisation and constraint based heuristic methods for advanced planning and scheduling systems, Int. J. Ind. Eng. Theory Appl. Pract., 23, 26-48, (2016)
[32] Rossi, F., Van Beek, P., Walsh, T.: Handbook of Constraint Programming. Elsevier, New York City (2006) · Zbl 1175.90011
[33] Senkul, P.; Toroslu, IH, An architecture for workflow scheduling under resource allocation constraints, Inf. Syst., 30, 399-422, (2005)
[34] Zhuk, D.: A proof of CSP dichotomy conjecture. In: Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS’17), pp. 331-342 (2017). https://doi.org/10.1109/FOCS.2017.38
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.