{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:36:23Z","timestamp":1770921383807,"version":"3.50.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-17801-5_4","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:55Z","timestamp":1770918775000},"page":"46-60","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards an\u00a0Algebraic Approach to\u00a0the\u00a0Reconfiguration CSP"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0560-5127","authenticated-orcid":false,"given":"Kei","family":"Kimura","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"4_CR1","unstructured":"Barto, L., Krokhin, A., Willard, R.: Polymorphisms, and how to use them. In: Krokhin, A., \u017divn\u00fd, S. (eds.) The Constraint Satisfaction Problem: Complexity and Approximability, vol.\u00a07, pp. 45\u201377. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"issue":"50","key":"4_CR2","doi-asserted-by":"publisher","first-page":"5215","DOI":"10.1016\/j.tcs.2009.08.023","volume":"410","author":"P Bonsma","year":"2009","unstructured":"Bonsma, P., Cereceda, L.: Finding paths between graph colourings: pspace-completeness and superpolynomial distances. Theor. Comput. Sci. 410(50), 5215\u20135226 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.08.023","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"4_CR3","doi-asserted-by":"publisher","first-page":"1708","DOI":"10.1016\/j.disc.2018.03.006","volume":"341","author":"RC Brewster","year":"2018","unstructured":"Brewster, R.C., Lee, J.B., Siggers, M.: Recolouring reflexive digraphs. Discret. Math. 341(6), 1708\u20131721 (2018). https:\/\/doi.org\/10.1016\/j.disc.2018.03.006","journal-title":"Discret. Math."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.05.015","volume":"639","author":"RC Brewster","year":"2016","unstructured":"Brewster, R.C., McGuinness, S., Moore, B., Noel, J.A.: A dichotomy theorem for circular colouring reconfiguration. Theor. Comput. Sci. 639, 1\u201313 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.05.015","journal-title":"Theor. Comput. Sci."},{"key":"4_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.jctb.2020.10.001","volume":"147","author":"R Brice\u00f1o","year":"2021","unstructured":"Brice\u00f1o, R., Bulatov, A., Dalmau, V., Larose, B.: Dismantlability, connectedness, and mixing in relational structures. J. Comb. Theory Ser. B 147, 37\u201370 (2021). https:\/\/doi.org\/10.1016\/j.jctb.2020.10.001","journal-title":"J. Comb. Theory Ser. B"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pp. 319\u2013330 (2017)","DOI":"10.1109\/FOCS.2017.37"},{"key":"4_CR7","doi-asserted-by":"publisher","unstructured":"Carvalho, C., Egri, L., Jackson, M., Niven, T.: On maltsev digraphs. Electr. J. Comb. 22, 1\u201332 (2015). https:\/\/doi.org\/10.37236\/4419","DOI":"10.37236\/4419"},{"issue":"1","key":"4_CR8","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1002\/jgt.20514","volume":"67","author":"L Cereceda","year":"2011","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colorings. J. Graph Theory 67(1), 69\u201382 (2011). https:\/\/doi.org\/10.1002\/jgt.20514","journal-title":"J. Graph Theory"},{"key":"4_CR9","unstructured":"Dechter, R.: Constraint Processing. Morgan Kaufmann, California (2003)"},{"key":"4_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejc.2023.103704","volume":"110","author":"A Dochtermann","year":"2023","unstructured":"Dochtermann, A., Singh, A.: Homomorphism complexes, reconfiguration, and homotopy for directed graphs. Eur. J. Comb. 110, 1\u201331 (2023). https:\/\/doi.org\/10.1016\/j.ejc.2023.103704","journal-title":"Eur. J. Comb."},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Dyer, M.E., Richerby, D.M.: On the complexity of $$\\#$$CSP. In: Proceedings of the forty-second ACM Symposium on Theory of Computing, pp. 725\u2013734 (2010). https:\/\/doi.org\/10.1145\/1806689.1806789","DOI":"10.1145\/1806689.1806789"},{"key":"4_CR12","doi-asserted-by":"publisher","unstructured":"Fujii, S., Iwamasa, Y., Kimura, K., Nozaki, Y., Suzuki, A.: Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles. J. Appl. Comput. Topol.9(21) (2025). https:\/\/doi.org\/10.1007\/s41468-025-00219-7","DOI":"10.1007\/s41468-025-00219-7"},{"key":"4_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2025.104238","volume":"131","author":"S Fujii","year":"2026","unstructured":"Fujii, S., Kimura, K., Nozaki, Y.: Homotopy types of Hom complexes of graph homomorphisms whose codomains are square-free. Eur. J. Comb. 131, 104238 (2026). https:\/\/doi.org\/10.1016\/j.ejc.2025.104238","journal-title":"Eur. J. Comb."},{"issue":"1","key":"4_CR14","doi-asserted-by":"publisher","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27(1), 95\u2013100 (1968). https:\/\/doi.org\/10.2140\/pjm.1968.27.95","journal-title":"Pac. J. Math."},{"key":"4_CR15","doi-asserted-by":"publisher","first-page":"2330","DOI":"10.1137\/07070440X","volume":"38","author":"P Gopalan","year":"2009","unstructured":"Gopalan, P., Kolaitis, P.G., Maneva, E., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. SIAM J. Comput. 38, 2330\u20132355 (2009)","journal-title":"SIAM J. Comput."},{"key":"4_CR16","unstructured":"Hatanaka, T., Ito, T., Zhou, X.: Complexity of reconfiguration problems for constraint satisfaction. arXiv preprint arXiv:1812.10629 (2018)"},{"issue":"12\u201314","key":"4_CR17","doi-asserted-by":"publisher","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"T Ito","year":"2011","unstructured":"Ito, T., Demaine, E.D., Harvey, N.J., Papadimitriou, C.H., Sideri, M., Uehara, R., Uno, Y.: On the complexity of reconfiguration problems. Theor. Comput. Sci. 412(12\u201314), 1054\u20131065 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR18","doi-asserted-by":"publisher","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: A unifying framework for tractable constraints. In: Montanari, U., Rossi, F. (eds.) CP 1995. LNCS, vol. 976, pp. 276\u2013291. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-60299-2_17","DOI":"10.1007\/3-540-60299-2_17"},{"key":"4_CR19","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/j.jcss.2016.07.008","volume":"84","author":"P Jonsson","year":"2017","unstructured":"Jonsson, P., Lagerkvist, V., Nordh, G., Zanuttini, B.: Strong partial clones and the time complexity of sat problems. J. Comput. Syst. Sci. 84, 52\u201378 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR20","unstructured":"Kimura, K.: Towards an algebraic approach to the reconfiguration CSP. arXiv: 2511.22914 (2025)"},{"issue":"2","key":"4_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3389411","volume":"12","author":"V Lagerkvist","year":"2020","unstructured":"Lagerkvist, V., Wahlstr\u00f6m, M.: Sparsification of sat and csp problems via tractable extensions. ACM Trans. Comput. Theory (TOCT) 12(2), 1\u201329 (2020)","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"4_CR22","doi-asserted-by":"publisher","unstructured":"Lagerkvist, V., Wahlstr\u00f6m, M.: The (coarse) fine-grained structure of NP-hard SAT and CSP problems. ACM Trans. Comput. Theory 14, 1\u201354 (2021). https:\/\/doi.org\/10.1145\/3492336","DOI":"10.1145\/3492336"},{"issue":"1","key":"4_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s10801-022-01161-y","volume":"57","author":"JB Lee","year":"2023","unstructured":"Lee, J.B., Noel, J.A., Siggers, M.: Recolouring homomorphisms to triangle-free reflexive graphs. J. Algeb. Comb. 57(1), 53\u201373 (2023). https:\/\/doi.org\/10.1007\/s10801-022-01161-y","journal-title":"J. Algeb. Comb."},{"issue":"1","key":"4_CR24","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1137\/23M1623690","volume":"39","author":"B L\u00e9v\u00eaque","year":"2025","unstructured":"L\u00e9v\u00eaque, B., M\u00fchlenthaler, M., Suzan, T.: Reconfiguration of digraph homomorphisms. SIAM J. Disc. Math. 39(1), 327\u2013360 (2025). https:\/\/doi.org\/10.1137\/23M1623690","journal-title":"SIAM J. Disc. Math."},{"key":"4_CR25","unstructured":"Matsushita, T.: Hom complexes of graphs whose codomains are square-free. arXiv preprint arXiv:2412.19144 (2024)"},{"key":"4_CR26","unstructured":"Meyer, S.: A dichotomy for finite abstract simplicial complexes. arXiv preprint arXiv:2408.08199 (2024)"},{"key":"4_CR27","doi-asserted-by":"publisher","unstructured":"Meyer, S., Opr\u0161al, J.: A topological proof of the hell-ne\u0161et\u0159il dichotomy. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 4507\u20134519. SIAM (2025). https:\/\/doi.org\/10.1137\/1.9781611978322.154","DOI":"10.1137\/1.9781611978322.154"},{"issue":"2","key":"4_CR28","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01069627","volume":"17","author":"BA Romov","year":"1981","unstructured":"Romov, B.A.: The algebras of partial functions and their invariants. Cybernetics 17(2), 157\u2013167 (1981). https:\/\/doi.org\/10.1007\/BF01069627","journal-title":"Cybernetics"},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"4_CR30","doi-asserted-by":"publisher","unstructured":"Schnider, P., Weber, S.: A topological version of schaefer\u2019s dichotomy theorem. In: 40th International Symposium on Computational Geometry (SoCG 2024), pp. 77\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPIcs.SoCG.2024.77","DOI":"10.4230\/LIPIcs.SoCG.2024.77"},{"key":"4_CR31","doi-asserted-by":"publisher","first-page":"173","DOI":"10.3233\/SAT190097","volume":"8","author":"KW Schwerdtfeger","year":"2014","unstructured":"Schwerdtfeger, K.W.: A computational trichotomy for connectivity of Boolean satisfiability. J. Satisfiabil. Boolean Model. Comput. 8, 173\u2013195 (2014)","journal-title":"J. Satisfiabil. Boolean Model. Comput."},{"key":"4_CR32","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/17M1122578","volume":"34","author":"M Wrochna","year":"2020","unstructured":"Wrochna, M.: Homomorphism reconfiguration via homotopy. SIAM J. Disc. Math. 34, 328\u2013350 (2020). https:\/\/doi.org\/10.1137\/17M1122578","journal-title":"SIAM J. Disc. Math."},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Zhuk, D.: A proof of CSP dichotomy conjecture. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, pp. 331\u2013342 (2017)","DOI":"10.1109\/FOCS.2017.38"},{"issue":"5","key":"4_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3402029","volume":"67","author":"D Zhuk","year":"2020","unstructured":"Zhuk, D.: A proof of the CSP dichotomy conjecture. J. ACM (JACM) 67(5), 1\u201378 (2020). https:\/\/doi.org\/10.1145\/3402029","journal-title":"J. ACM (JACM)"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Zivny, S.: The Complexity of Valued Constraint Satisfaction Problems. Springer, Cham (2012)","DOI":"10.1007\/978-3-642-33974-5"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:52:58Z","timestamp":1770918778000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}