Galois connections for patterns: an algebra of labelled graphs. (English) Zbl 1467.68176

Cochez, Michael (ed.) et al., Graph structures for knowledge representation and reasoning. 6th international workshop, GKR 2020, virtual event, September 5, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12640, 125-150 (2021).
Summary: A pattern is a generic instance of a binary constraint satisfaction problem (CSP) in which the compatibility of certain pairs of variable-value assignments may be unspecified. The notion of forbidden pattern has led to the discovery of several novel tractable classes for the CSP. However, for this field to come of age it is time for a theoretical study of the algebra of patterns. We present a Galois connection between lattices composed of sets of forbidden patterns and sets of generic instances, and investigate its consequences. We then extend patterns to augmented patterns and exhibit a similar Galois connection. Augmented patterns are a more powerful language than flat (i.e. non-augmented) patterns, as we demonstrate by showing that, for any \(k \ge 1\), instances with tree-width bounded by \(k\) cannot be specified by forbidding a finite set of flat patterns but can be specified by a finite set of augmented patterns. A single finite set of augmented patterns can also describe the class of instances such that each instance has a weak near-unanimity polymorphism of arity \(k\) (thus covering all tractable language classes). We investigate the power of forbidding augmented patterns and discuss their potential for describing new tractable classes.
For the entire collection see [Zbl 1467.68005].


68T30 Knowledge representation
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
06A15 Galois correspondences, closure operators (in relation to ordered sets)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Barto, L., Krokhin, A.A., Willard, R.: Polymorphisms, and how to use them. In: Krokhin, A., Živný, S. (eds.) [32], pp. 1-44. doi:10.4230/DFU.Vol7.15301.1
[2] Birkhoff, G., Lattice Theory (1967), New York: AMS Colloquium Publications, American Mathematical Society, New York · Zbl 0153.02501
[3] Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15-17 October 2017, pp. 319-330. IEEE Computer Society (2017). doi:10.1109/FOCS.2017.37
[4] Bulatov, AA; Jeavons, P.; Krokhin, AA, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34, 3, 720-742 (2005) · Zbl 1071.08002
[5] Bulin, J.; Delic, D.; Jackson, M.; Niven, T., A finer reduction of constraint problems to digraphs, Log. Methods Comput. Sci., 11, 4, 1-33 (2015) · Zbl 1409.05094
[6] Carbonnel, C.; Rueher, M., The dichotomy for conservative constraint satisfaction is polynomially decidable, Principles and Practice of Constraint Programming, 130-146 (2016), Cham: Springer, Cham
[7] Carbonnel, C.; Cohen, DA; Cooper, MC; Živný, S., On singleton arc consistency for CSPs defined by monotone patterns, Algorithmica, 81, 4, 1699-1727 (2019) · Zbl 1421.68151
[8] Carbonnel, C.; Cooper, MC, Tractability in constraint satisfaction problems: a survey, Constraints, 21, 2, 115-144 (2016) · Zbl 1334.90220
[9] Cohen, DA; Cooper, MC; Creed, P.; Marx, D.; Salamon, AZ, The tractability of CSP classes defined by forbidden patterns, J. Artif. Intell. Res. (JAIR), 45, 47-78 (2012) · Zbl 1253.68296
[10] Cohen, DA; Cooper, MC; Jeavons, PG; Krokhin, AA; Powell, R.; Živný, S., Binarisation for valued constraint satisfaction problems, SIAM J. Discret. Math., 31, 4, 2279-2300 (2017) · Zbl 1477.68121
[11] Cohen, DA; Cooper, MC; Jeavons, PG; Živný, S., Binary constraint satisfaction problems defined by excluded topological minors, Inf. Comput., 264, 12-31 (2019) · Zbl 1408.68130
[12] Cooper, MC; O’Sullivan, B., Beyond consistency and substitutability, Principles and Practice of Constraint Programming, 256-271 (2014), Cham: Springer, Cham
[13] Cooper, MC; Cohen, DA; Jeavons, P., Characterising tractable constraints, Artif. Intell., 65, 2, 347-361 (1994) · Zbl 0803.68053
[14] 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
[15] 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
[16] Cooper, MC; Jeavons, PG; Salamon, AZ, Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination, Artif. Intell., 174, 9-10, 570-584 (2010) · Zbl 1205.68372
[17] Cooper, MC; Živný, S., Hybrid tractability of valued constraint problems, Artif. Intell., 175, 9-10, 1555-1569 (2011) · Zbl 1225.68243
[18] Cooper, M.C., Živný, S.: Hybrid tractable classes of constraint problems. In: Krokhin, A., Živný, S. (eds.) [32], pp. 113-135. doi:10.4230/DFU.Vol7.15301.4
[19] 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). doi:10.23638/LMCS-13(4:26)2017 · Zbl 1387.68117
[20] Courcelle, B.; Mosbah, M., Monadic second-order evaluations on tree-decomposable graphs, Theor. Comput. Sci., 109, 1-2, 49-82 (1993) · Zbl 0789.68083
[21] Davey, BA; Priestley, HA, Introduction to Lattices and Order (2002), Cambridge: Cambridge University Press, Cambridge
[22] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 3, 353-366 (1989) · Zbl 0665.68084
[23] Feder, T.; Vardi, MY, The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1998) · Zbl 0914.68075
[24] Freuder, EC, A sufficient condition for backtrack-bounded search, J. ACM, 32, 4, 755-761 (1985) · Zbl 0633.68096
[25] Green, MJ; Cohen, DA, Domain permutation reduction for constraint satisfaction problems, Artif. Intell., 172, 8-9, 1094-1118 (2008) · Zbl 1183.68309
[26] Grohe, M., The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1, 1:1-1:24 (2007) · Zbl 1312.68101
[27] Jeavons, P., On the algebraic structure of combinatorial problems, Theor. Comput. Sci., 200, 1-2, 185-204 (1998) · Zbl 0915.68074
[28] Jeavons, P.; Cohen, DA; Gyssens, M., Closure properties of constraints, J. ACM, 44, 4, 527-548 (1997) · Zbl 0890.68064
[29] Jeavons, P.; Cooper, MC, Tractable constraints on ordered domains, Artif. Intell., 79, 2, 327-339 (1995) · Zbl 1013.68503
[30] Jégou, P.: Decomposition of domains based on the micro-structure of finite constraint-satisfaction problems. In: Fikes, R., Lehnert, W.G. (eds.) Proceedings of the 11th National Conference on Artificial Intelligence, Washington, DC, USA, pp. 731-736. AAAI Press/The MIT Press (1993). http://www.aaai.org/Library/AAAI/1993/aaai93-109.php
[31] Knuth, DE, Stable Marriage and Its Relation to Other Combinatorial Problems, CRM Proceedings & Lecture Notes (1996), Providence: American Mathematical Society, Providence
[32] Krokhin, A.A., Živný, S. (eds.): The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). http://www.dagstuhl.de/dagpub/978-3-95977-003-3
[33] Kun, G.; Nešetřil, J., Forbidden lifts (NP and CSP for combinatorialists), Eur. J. Comb., 29, 4, 930-945 (2008) · Zbl 1213.68323
[34] Ladner, RE, On the structure of polynomial time reducibility, J. ACM, 22, 1, 155-171 (1975) · Zbl 0322.68028
[35] Mouelhi, AE, Tractable classes for CSPs of arbitrary arity: from theory to practice, Constraints, 22, 1, 97-98 (2017)
[36] Naanaa, W., Unifying and extending hybrid tractable classes of CSPs, J. Exp. Theor. Artif. Intell., 25, 4, 407-424 (2013)
[37] Naanaa, W.: Extending the broken triangle property tractable class of binary CSPs. In: Bassiliades, N., Bikakis, A., Vrakas, D., Vlahavas, I.P., Vouros, G.A. (eds.) Proceedings of the 9th Hellenic Conference on Artificial Intelligence, SETN 2016, Thessaloniki, Greece, pp. 3:1-3:6. ACM (2016). doi:10.1145/2903220.2903230
[38] Régin, J.: A filtering algorithm for constraints of difference in CSPs. In: Hayes-Roth, B., Korf, R.E. (eds.) Proceedings of the 12th National Conference on Artificial Intelligence, vol. 1, pp. 362-367. AAAI Press/The MIT Press (1994). http://www.aaai.org/Library/AAAI/1994/aaai94-055.php
[39] Siggers, MH, A strong Mal’cev condition for locally finite varieties omitting the unary type, Algebra Univers., 64, 1-2, 15-20 (2010) · Zbl 1216.08002
[40] Stergiou, K.; Samaras, N., Binary encodings of non-binary constraint satisfaction problems: algorithms and experimental results, J. Artif. Intell. Res. (JAIR), 24, 641-684 (2005) · Zbl 1080.68673
[41] Zhuk, D., A proof of the CSP dichotomy conjecture, J. ACM, 67, 5, 30:1-30:78 (2020) · Zbl 07273097
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.