{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:18:03Z","timestamp":1740122283614,"version":"3.37.3"},"reference-count":72,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T00:00:00Z","timestamp":1679702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T00:00:00Z","timestamp":1679702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002957","name":"Technische Universit\u00e4t Dresden","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We find an orientation of a tree with 20 vertices such that the corresponding fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove that for every orientation of a tree with fewer vertices the corresponding CSP can be solved in polynomial time. We also compute the smallest tree that is NL-hard (assuming L\u2260NL), the smallest tree that cannot be solved by arc consistency, and the smallest tree that cannot be solved by Datalog. Our experimental results also support a conjecture of Bul\u00edn concerning a question of Hell, Ne\u0161et\u0159il and Zhu, namely that \u2018easy trees lack the ability to count\u2019. Most proofs are computer-based and make use of the most recent universal-algebraic theory about the complexity of finite-domain CSPs. However, further ideas are required because of the huge number of orientations of trees. In particular, we use the well-known fact that it suffices to study orientations of trees that are cores and show how to efficiently decide whether a given orientation of a tree is a core using the arc-consistency procedure. Moreover, we present a method to generate orientations of trees that are cores that works well in practice. In this way we found interesting examples for the open research problem to classify finite-domain CSPs in NL.<\/jats:p>","DOI":"10.1007\/s10601-023-09341-8","type":"journal-article","created":{"date-parts":[[2023,3,25]],"date-time":"2023-03-25T12:02:22Z","timestamp":1679745742000},"page":"105-137","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The smallest hard trees"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":false,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5235-8715","authenticated-orcid":false,"given":"Jakub","family":"Bul\u00edn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2360-9364","authenticated-orcid":false,"given":"Florian","family":"Starke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4978-0928","authenticated-orcid":false,"given":"Michael","family":"Wernthaler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,25]]},"reference":[{"key":"9341_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F. N., & Cosmadakis, S. S. (1989). Expressiveness of restricted recursive queries (extended abstract). In D. S. Johnson (Ed.) Proceedings of the 21st Annual ACM Symposium on Theory of Computing (pp. 113\u2013126). Washigton: ACM.","DOI":"10.1145\/73007.73018"},{"key":"9341_CR2","doi-asserted-by":"crossref","unstructured":"Barto, L. (2011). The dichotomy for conservative constraint satisfaction problems revisited. In Proceedings of the Symposium on Logic in Computer Science (LICS), Toronto, Canada.","DOI":"10.1109\/LICS.2011.25"},{"issue":"1","key":"9341_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.4153\/CJM-2011-087-3","volume":"65","author":"L Barto","year":"2013","unstructured":"Barto, L. (2013). Finitely related algebras in congruence distributive varieties have near unanimity terms. Canadian Journal of Mathematics, 65(1), 3\u201321.","journal-title":"Canadian Journal of Mathematics"},{"issue":"5","key":"9341_CR4","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1142\/S0218196713500215","volume":"23","author":"L Barto","year":"2013","unstructured":"Barto, L., & Bul\u00edn, J. (2013). CSP dichotomy for special polyads. International Journal of Algebra and Computation, 23(5), 1151\u20131174.","journal-title":"International Journal of Algebra and Computation"},{"key":"9341_CR5","doi-asserted-by":"crossref","unstructured":"Barto, L., & Kozik, M. (2009). Constraint satisfaction problems of bounded width. In Proceedings of Symposium on Foundations of Computer Science (FOCS), pp. 595\u2013603.","DOI":"10.1109\/FOCS.2009.32"},{"issue":"07","key":"9341_CR6","first-page":"1","volume":"8\/1","author":"L Barto","year":"2012","unstructured":"Barto, L., & Kozik, M. (2012). Absorbing subalgebras, cyclic terms and the constraint satisfaction problem. Logical Methods in Computer Science, 8\/1 (07), 1\u201326.","journal-title":"Logical Methods in Computer Science"},{"issue":"1","key":"9341_CR7","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2556646","volume":"61","author":"L Barto","year":"2014","unstructured":"Barto, L., & Kozik, M. (2014). Constraint satisfaction problems solvable by local consistency methods. Journal of the ACM, 61(1), 3:1\u20133:19.","journal-title":"Journal of the ACM"},{"issue":"9","key":"9341_CR8","doi-asserted-by":"publisher","first-page":"2921","DOI":"10.1090\/S0002-9939-09-09883-9","volume":"137","author":"L Barto","year":"2009","unstructured":"Barto, L., Kozik, M., Mar\u00f3ti, M., & Niven, T. (2009). CSP dichotomy for special triads. Proceedings of the American Mathematical Society, 137(9), 2921\u20132934.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"9341_CR9","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M., Mar\u00f3ti, M., & Niven, T. (2009). Erratum to: CSP dichotomy for special triads Available from the website of the first author.","DOI":"10.1090\/S0002-9939-09-09883-9"},{"key":"9341_CR10","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1137\/070708093"},{"key":"9341_CR11","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M., & Willard, R. (2012). Near unanimity constraints have bounded pathwidth duality. In Proceedings of the 27th ACM\/IEEE Symposium on Logic in Computer Science (LICS), pp. 125\u2013134.","DOI":"10.1109\/LICS.2012.24"},{"key":"9341_CR12","unstructured":"Barto, L., Krokhin, A., & Willard, R. (2017). Polymorphisms, and how to use them. In A. Krokhin S. \u017eivn\u00fd (Eds.) The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups (pp. 1\u201344). Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl."},{"issue":"1","key":"9341_CR13","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s11856-017-1621-9","volume":"223","author":"L Barto","year":"2018","unstructured":"Barto, L., Opr\u0161al, J., & Pinsker, M. (2018). The wonderland of reflections. Israel Journal of Mathematics, 223(1), 363\u2013398.","journal-title":"Israel Journal of Mathematics"},{"key":"9341_CR14","doi-asserted-by":"crossref","unstructured":"Bodirsky, M. (2021). Complexity of Infinite-Domain constraint satisfaction. In Lecture notes in logic (52). Cambridge: Cambridge University Press.","DOI":"10.1017\/9781107337534"},{"key":"9341_CR15","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., & Bodor, B. (2021). Canonical polymorphisms of Ramsey structures and the unique interpolation property. In Proceedings of the Symposium on Logic in Computer Science (LICS).","DOI":"10.1109\/LICS52264.2021.9470683"},{"key":"9341_CR16","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1613\/jair.5260","volume":"58","author":"M Bodirsky","year":"2017","unstructured":"Bodirsky, M., & Jonsson, P. (2017). A model-theoretic view on qualitative constraint reasoning. Journal of Artificial Intelligence Research, 58, 339\u2013385.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9341_CR17","doi-asserted-by":"crossref","unstructured":"Bulatov, A. A. (2003). Tractable conservative constraint satisfaction problems. In Proceedings of the Symposium on Logic in Computer Science (LICS), (pp. 321\u2013330). Ottawa, Canada.","DOI":"10.1109\/LICS.2003.1210072"},{"key":"9341_CR18","unstructured":"Bulatov, A. A. (2009). Bounded relational width Manuscript."},{"issue":"2","key":"9341_CR19","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/j.jcss.2015.07.004","volume":"82","author":"AA Bulatov","year":"2016","unstructured":"Bulatov, A. A. (2016). Conservative constraint satisfaction re-revisited. Journal Computer and System Sciences, 82(2), 347\u2013356. ArXiv:1408.3690.","journal-title":"Journal Computer and System Sciences"},{"key":"9341_CR20","doi-asserted-by":"crossref","unstructured":"Bulatov, A. A. (2017). A dichotomy theorem for nonuniform CSPs. In 58th IEEE, Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15\u201317, pp. 319\u2013330.","DOI":"10.1109\/FOCS.2017.37"},{"key":"9341_CR21","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"AA Bulatov","year":"2005","unstructured":"Bulatov, A. A., Krokhin, A. A., & Jeavons, P. G. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34, 720\u2013742.","journal-title":"SIAM Journal on Computing"},{"key":"9341_CR22","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.ejc.2017.10.001","volume":"69","author":"J Bul\u00edn","year":"2018","unstructured":"Bul\u00edn, J. (2018). On the complexity of H-coloring for special oriented trees. European Journal of Combinatorics, 69, 54\u201375.","journal-title":"European Journal of Combinatorics"},{"key":"9341_CR23","doi-asserted-by":"crossref","unstructured":"Bul\u00edn, J., Deli\u0107, D., Jackson, M., & Niven, T. (2015). A finer reduction of constraint problems to digraphs. Log. Methods Comput. Sci. 11(4).","DOI":"10.2168\/LMCS-11(4:18)2015"},{"key":"9341_CR24","doi-asserted-by":"publisher","first-page":"3188","DOI":"10.1016\/j.tcs.2010.05.016","volume":"411","author":"C Carvalho","year":"2010","unstructured":"Carvalho, C., Dalmau, V., & Krokhin, A. (2010). CSP Duality and trees of bounded pathwidth. Theoretical Computer Science, 411, 3188\u20133208.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"9341_CR25","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/3134757","volume":"9","author":"H Chen","year":"2017","unstructured":"Chen, H., & Larose, B. (2017). Asking the metaquestions in constraint tractability. TOCT, 9(3), 11:1\u201311:27.","journal-title":"TOCT"},{"key":"9341_CR26","unstructured":"Chen, H., & Mengel, S. (2015). A trichotomy in the complexity of counting answers to conjunctive queries. In 18th International Conference on Database Theory, ICDT 2015, March 23-27, 2015, Brussels, Belgium, pp. 110\u2013126."},{"key":"9341_CR27","unstructured":"Dalmau, V. (2000). Computational complexity of problems over generalized formulas phD-thesis at the Departament de Llenguatges i Sistemes inform\u00e1tics at the Universitat polit\u00e9cnica de Catalunya."},{"key":"9341_CR28","doi-asserted-by":"crossref","unstructured":"Dalmau, V. (2005). Linear Datalog and bounded path duality of relational structures. Logical Methods in Computer Science 1(1).","DOI":"10.2168\/LMCS-1(1:5)2005"},{"issue":"4","key":"9341_CR29","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1016\/j.ejc.2007.11.020","volume":"29","author":"V Dalmau","year":"2008","unstructured":"Dalmau, V., & Krokhin, A. A. (2008). Majority constraints have bounded pathwidth duality. European Journal of Combinatorics, 29(4), 821\u2013837.","journal-title":"European Journal of Combinatorics"},{"key":"9341_CR30","doi-asserted-by":"crossref","unstructured":"Dalmau, V., & Pearson, J. (1999). Closure functions and width 1 problems. In Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), pp. 159\u2013173.","DOI":"10.1007\/978-3-540-48085-3_12"},{"key":"9341_CR31","volume-title":"Graph theory","author":"R Diestel","year":"2005","unstructured":"Diestel, R. (2005). Graph theory, 3rd edn. New York: Springer\u2013Verlag.","edition":"3rd edn."},{"key":"9341_CR32","doi-asserted-by":"crossref","unstructured":"Egri, L., Larose, B., & Tesson, P. (2007). Symmetric datalog and constraint satisfaction problems in logspace. In Proceedings of the Symposium on Logic in Computer Science (LICS), pp. 193\u2013202.","DOI":"10.1109\/LICS.2007.47"},{"key":"9341_CR33","doi-asserted-by":"crossref","unstructured":"Egri, L, Larose, B., & Tesson, P. (2008). Directed st-connectivity is not expressible in symmetric datalog. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II, ICALP \u201908 (pp. 172\u2013183). Berlin: Springer-Verlag.","DOI":"10.1007\/978-3-540-70583-3_15"},{"issue":"4","key":"9341_CR34","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/S0895480199383353","volume":"14","author":"T Feder","year":"2001","unstructured":"Feder, T. (2001). Classification of homomorphisms to oriented cycles and of k-partite satisfiability. SIAM Journal on Discrete Mathematics, 14(4), 471\u2013480.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9341_CR35","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1999","unstructured":"Feder, T., & Vardi, M. Y. (1999). The computational structure of monotone monadic SNP, and constraint satisfaction: a study through Datalog and group theory. SIAM Journal on Computing, 28, 57\u2013104.","journal-title":"SIAM Journal on Computing"},{"key":"9341_CR36","volume-title":"CSPS of orientations of trees","author":"J Fischer","year":"2015","unstructured":"Fischer, J. (2015). CSPS of orientations of trees. TU Dresden: Master thesis."},{"issue":"2","key":"9341_CR37","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1023\/B:CONS.0000024049.41091.71","volume":"9","author":"R Gault","year":"2004","unstructured":"Gault, R., & Jeavons, P. (2004). Implementing a test for tractability. Constraints An International Journal, 9(2), 139\u2013160.","journal-title":"Constraints An International Journal"},{"key":"9341_CR38","unstructured":"Gutjahr, W. (1991). Graph colourings. PhD Thesis, Free University Berlin."},{"issue":"1","key":"9341_CR39","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(92)90294-K","volume":"35","author":"W Gutjahr","year":"1992","unstructured":"Gutjahr, W., Welzl, E., & Woeginger, G. J. (1992). Polynomial graph-colorings. Discrete Applied Mathematics, 35(1), 29\u201345.","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"9341_CR40","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0166-218X(96)00099-6","volume":"70","author":"P Hell","year":"1996","unstructured":"Hell, P., Nesetril, J., & Zhu, X. (1996). Complexity of tree homomorphisms. Discret. Appl Math., 70(1), 23\u201336.","journal-title":"Discret. Appl Math."},{"key":"9341_CR41","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P Hell","year":"1990","unstructured":"Hell, P., & Ne\u0161et\u0159il, J. (1990). On the complexity of H-coloring. Journal of Combinatorial Theory Series B, 48, 92\u2013110.","journal-title":"Journal of Combinatorial Theory Series B"},{"key":"9341_CR42","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0012-365X(92)90282-K","volume":"109","author":"P Hell","year":"1992","unstructured":"Hell, P., & Ne\u0161et\u0159il, J. (1992). The core of a graph. Discrete Mathematics, 109, 117\u2013126.","journal-title":"Discrete Mathematics"},{"key":"9341_CR43","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and homomorphisms","author":"P Hell","year":"2004","unstructured":"Hell, P., & Ne\u0161et\u0159il, J. (2004). Graphs and homomorphisms. Oxford: Oxford University Press."},{"issue":"4","key":"9341_CR44","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1090\/S0002-9947-96-01537-1","volume":"348","author":"P Hell","year":"1996","unstructured":"Hell, P., Ne\u0161et\u0159il, J., & Zhu, X. (1996). Duality and polynomial testing of tree homomorphisms. TAMS, 348(4), 1281\u20131297.","journal-title":"TAMS"},{"key":"9341_CR45","doi-asserted-by":"crossref","unstructured":"Hell, P., & Rafiey, A. (2011). The dichotomy of list homomorphisms for digraphs. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201911 (pp. 1703\u20131713). USA: Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611973082.131"},{"key":"9341_CR46","doi-asserted-by":"crossref","unstructured":"Hobby, D., & McKenzie, R. (1988). The structure of finite algebras, volume 76 of Contemporary Mathematics American Mathematical Society.","DOI":"10.1090\/conm\/076"},{"key":"9341_CR47","volume-title":"Descriptive complexity. Graduate texts in computer science","author":"N Immerman","year":"1998","unstructured":"Immerman, N. (1998). Descriptive complexity. Graduate texts in computer science. New York: Springer."},{"key":"9341_CR48","doi-asserted-by":"crossref","unstructured":"Jeavons, P., Cohen, D., & Gyssens, M. (1996). A test for tractability. In E. C. Freuder (Ed.) Principles and Practice of Constraint Programming \u2014 CP96 (pp. 267\u2013281). Berlin: Springer Berlin Heidelberg.","DOI":"10.1007\/3-540-61551-2_80"},{"issue":"4","key":"9341_CR49","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., & Gyssens, M. (1997). Closure properties of constraints. Journal of the ACM, 44(4), 527\u2013548.","journal-title":"Journal of the ACM"},{"issue":"3","key":"9341_CR50","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D. S., Yannakakis, M., & Papadimitriou, C. H. (1988). On generating all maximal independent sets. Information Processing Letters, 27(3), 119\u2013123.","journal-title":"Information Processing Letters"},{"key":"9341_CR51","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.ejc.2010.11.002","volume":"32","author":"A Kazda","year":"2011","unstructured":"Kazda, A. (2011). Maltsev digraphs have a majority polymorphism. European Journal of Combinatorics, 32, 390\u2013397.","journal-title":"European Journal of Combinatorics"},{"key":"9341_CR52","unstructured":"Kazda, A. (2018). n-permutability and linear Datalog implies symmetric Datalog. Logical Methods in Computer Science, Volume 14 Issue 2."},{"issue":"1","key":"9341_CR53","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00012-015-0358-8","volume":"75","author":"A Kazda","year":"2019","unstructured":"Kazda, A. (2019). CSP for binary conservative relational structures. Algebra Universalis, 75(1), 75\u201384.","journal-title":"Algebra Universalis"},{"key":"9341_CR54","doi-asserted-by":"crossref","unstructured":"Kearnes, K. A., & Kiss, E. W. (2013). The Shape of Congruence Lattices, volume 222 (1046) of Memoirs of the American Mathematical Society American Mathematical Society.","DOI":"10.1090\/S0065-9266-2012-00667-8"},{"issue":"1","key":"9341_CR55","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00012-014-0289-9","volume":"72","author":"KA Kearnes","year":"2015","unstructured":"Kearnes, K. A., Markovi\u0107, P., & McKenzie, R. (2015). Optimal strong Mal\u2019cev conditions for omitting type 1 in locally finite varieties. Algebra Universalis, 72(1), 91\u2013100.","journal-title":"Algebra Universalis"},{"key":"9341_CR56","doi-asserted-by":"crossref","unstructured":"Kozik, M. (2016). 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 \u201916 (pp. 633\u2013641). New York: Association for Computing Machinery.","DOI":"10.1145\/2933575.2934510"},{"issue":"3","key":"9341_CR57","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00012-015-0327-2","volume":"73","author":"M Kozik","year":"2015","unstructured":"Kozik, M., Krokhin, A., Valeriote, M., & Willard, R. (2015). Characterizations of several Maltsev conditions. Algebra universalis, 73(3), 205\u2013224.","journal-title":"Algebra universalis"},{"issue":"18","key":"9341_CR58","doi-asserted-by":"publisher","first-page":"1629","DOI":"10.1016\/j.tcs.2008.12.048","volume":"410","author":"B Larose","year":"2009","unstructured":"Larose, B., & Tesson, P. (2009). Universal algebra and hardness results for constraint satisfaction problems. Theoretical Computer Science, 410(18), 1629\u20131647.","journal-title":"Theoretical Computer Science"},{"key":"9341_CR59","doi-asserted-by":"crossref","unstructured":"Larose, B., Valeriote, M., & Z\u00e1dori, L. (2009). Omitting types, bounded width and the ability to count. International Journal of Algebra and Computation 19(5).","DOI":"10.1142\/S021819670900524X"},{"key":"9341_CR60","doi-asserted-by":"crossref","unstructured":"\u0141uczak, T., & Ne\u0161et\u0159il, J. (2006). When is a random graph projective? Eur. Journal Comb. 27(7).","DOI":"10.1016\/j.ejc.2006.06.010"},{"key":"9341_CR61","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"AK Mackworth","year":"1977","unstructured":"Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8, 99\u2013118.","journal-title":"Artificial Intelligence"},{"issue":"3-4","key":"9341_CR62","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00012-008-2122-9","volume":"59","author":"M Mar\u00f3ti","year":"2008","unstructured":"Mar\u00f3ti, M., & McKenzie, R. (2008). Existence theorems for weakly symmetric operations. Algebra Universalis, 59(3-4), 463\u2013489.","journal-title":"Algebra Universalis"},{"key":"9341_CR63","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B. D., & Piperno, A. (2014). Practical graph isomorphism, ii. Journal of Symbolic Computation, 60, 94\u2013112.","journal-title":"Journal of Symbolic Computation"},{"key":"9341_CR64","doi-asserted-by":"crossref","unstructured":"Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J., & Tack, G. (2007). Minizinc: Towards a standard CP modelling language. In C. Bessi\u00e8re (Ed.) Principles and Practice of Constraint Programming \u2013 CP 2007 (pp. 529\u2013543). Berlin: Springer Berlin Heidelberg.","DOI":"10.1007\/978-3-540-74970-7_38"},{"key":"9341_CR65","unstructured":"Opr\u0161al, J. (2022). PCSP Tools https:\/\/github.com\/jakub-oprsal\/pcsptools."},{"key":"9341_CR66","doi-asserted-by":"crossref","unstructured":"Sabin, D., & Freuder, E. C. (1994). Contradicting conventional wisdom in constraint satisfaction. In ECAI.","DOI":"10.1007\/3-540-58601-6_86"},{"key":"9341_CR67","unstructured":"Schulte, C., Lagerkvist, M. Z., & Tack, G. (2010). Gecode generic constraint development environment. http:\/\/www.gecode.org\/."},{"issue":"1","key":"9341_CR68","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s00012-010-0082-3","volume":"64","author":"MH Siggers","year":"2010","unstructured":"Siggers, M. H. (2010). A strong Mal\u2019cev condition for varieties omitting the unary type. Algebra Universalis, 64(1), 15\u201320.","journal-title":"Algebra Universalis"},{"key":"9341_CR69","volume-title":"CSP Over oriented trees","author":"W Tatarko","year":"2019","unstructured":"Tatarko, W. (2019). CSP Over oriented trees. Bachelor thesis: Charles University Prague."},{"key":"9341_CR70","unstructured":"Taylor, P. Algorithm for generating all unlabeled trees with n nodes? Computer Science Stack Exchange. https:\/\/cs.stackexchange.com\/q\/103287 (version: 2019-01-23)."},{"issue":"5","key":"9341_CR71","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/3402029","volume":"67","author":"D Zhuk","year":"2020","unstructured":"Zhuk, D. (2020). A proof of the CSP, dichotomy conjecture. Journal of ACM, 67(5), 30:1\u201330:78.","journal-title":"Journal of ACM"},{"key":"9341_CR72","doi-asserted-by":"crossref","unstructured":"Zhuk, D. N. (2017). A proof of CSP dichotomy conjecture. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, pp. 331\u2013342.","DOI":"10.1109\/FOCS.2017.38"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09341-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09341-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09341-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,4]],"date-time":"2023-08-04T02:08:09Z","timestamp":1691114889000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09341-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,25]]},"references-count":72,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9341"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09341-8","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2023,3,25]]},"assertion":[{"value":"3 January 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 March 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Competing interests"}}]}}