{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T23:45:48Z","timestamp":1767829548204,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T00:00:00Z","timestamp":1693526400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T00:00:00Z","timestamp":1696982400000},"content-version":"vor","delay-in-days":40,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004955","name":"\u00d6sterreichische Forschungsf\u00f6rderungsgesellschaft","doi-asserted-by":"publisher","award":["P32441"],"award-info":[{"award-number":["P32441"]}],"id":[{"id":"10.13039\/501100004955","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001821","name":"Vienna Science and Technology Fund","doi-asserted-by":"publisher","award":["ICT19-065"],"award-info":[{"award-number":["ICT19-065"]}],"id":[{"id":"10.13039\/501100001821","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V00252X\/1"],"award-info":[{"award-number":["EP\/V00252X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The constraint satisfaction problem (CSP) is among the most studied computational problems. While NP-hard, many tractable subproblems have been identified (Bulatov 2017, Zhuk 2017) Backdoors, introduced by Williams, Gomes, and Selman \n(2003), gradually extend such a tractable class to all CSP instances of bounded distance to the class. Backdoor size provides a natural but rather crude distance measure between a CSP instance and a tractable class. Backdoor depth, introduced by M\u00e4hlmann, Siebertz, and Vigny \n(2021) for SAT, is a more refined distance measure, which admits the parallel utilization of different backdoor variables. Bounded backdoor size implies bounded backdoor depth, but there are instances of constant backdoor depth and arbitrarily large backdoor size. Dreier, Ordyniak, and Szeider \n(2022) provided fixed-parameter algorithms for finding backdoors of small depth into the classes of Horn and Krom formulas. In this paper, we consider backdoor depth for CSP. We consider backdoors w.r.t. tractable subproblems <jats:inline-formula><jats:alternatives><jats:tex-math>$$C_\\Gamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>C<\/mml:mi>\n                    <mml:mi>\u0393<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the CSP defined by a constraint language <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\Gamma }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0393<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, i.e., where all the constraints use relations from the language <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\Gamma }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0393<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Building upon Dreier et al.\u2019s game-theoretic approach and their notion of separator obstructions, we show that for any finite, tractable, semi-conservative constraint language <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\Gamma }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0393<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the CSP is fixed-parameter tractable parameterized by the backdoor depth into\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$C_{\\varvec{\\Gamma }}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>C<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>\u0393<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> plus the domain size. With backdoors of low depth, we reach classes of instances that require backdoors of arbitrary large size. Hence, our results strictly generalize several known results for CSP that are based on backdoor size.<\/jats:p>","DOI":"10.1007\/s10601-023-09362-3","type":"journal-article","created":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T05:02:22Z","timestamp":1697000542000},"page":"450-471","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["CSP beyond tractable constraint languages"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2662-5303","authenticated-orcid":false,"given":"Jan","family":"Dreier","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1935-651X","authenticated-orcid":false,"given":"Sebastian","family":"Ordyniak","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8994-1656","authenticated-orcid":false,"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,11]]},"reference":[{"issue":"2","key":"9362_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10601-015-9198-6","volume":"21","author":"C Carbonnel","year":"2016","unstructured":"Carbonnel, C., & Cooper, M. C. (2016). Tractability in constraint satisfaction problems: a survey. Constraints, 21(2), 115\u2013144.","journal-title":"Constraints"},{"key":"9362_CR2","doi-asserted-by":"publisher","unstructured":"Bulatov, A.A. (2017). A dichotomy theorem for nonuniform CSPs. In C.\u00a0Umans (Ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, (pp. 319\u2013330). IEEE Computer Society. https:\/\/doi.org\/10.1109\/FOCS.2017.37.","DOI":"10.1109\/FOCS.2017.37"},{"key":"9362_CR3","doi-asserted-by":"publisher","unstructured":"Cooper, M. C., Cohen, D. A., & Jeavons, P. (1994). Characterising tractable constraints. Artificial Intelligence, 65(2), 347\u2013361. https:\/\/doi.org\/10.1016\/0004-3702(94)90021-3.","DOI":"10.1016\/0004-3702(94)90021-3"},{"key":"9362_CR4","doi-asserted-by":"crossref","unstructured":"Cohen, D., & Jeavons, P. (2006). The complexity of constraint languages. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of Constraint Programming (8th ed., Vol. I, pp. 245\u2013280). Elsevier.","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"9362_CR5","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J. (1978). The complexity of satisfiability problems. In Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978), (pp. 216\u2013226). ACM.","DOI":"10.1145\/800133.804350"},{"key":"9362_CR6","doi-asserted-by":"publisher","unstructured":"Zhuk, D. (2017). A proof of CSP dichotomy conjecture. In C. Umans (Ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017 (pp. 331\u2013342). IEEE Computer Society. https:\/\/doi.org\/10.1109\/FOCS.2017.38.","DOI":"10.1109\/FOCS.2017.38"},{"key":"9362_CR7","unstructured":"Cohen, D., Jeavons, P., & Gyssens, M. (2005). A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In International Joint Conferences on Artificial Intelligence (IJCAI-05), (pp. 72\u201377)."},{"issue":"2","key":"9362_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/S0004-3702(00)00078-3","volume":"124","author":"G Gottlob","year":"2000","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (2000). A comparison of structural CSP decomposition methods. Artificial Intelligence, 124(2), 243\u2013282.","journal-title":"Artificial Intelligence"},{"issue":"3","key":"9362_CR9","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jcss.2001.1809","volume":"64","author":"G Gottlob","year":"2002","unstructured":"Gottlob, G., Leone, N., & Scarcello, F. (2002). Hypertree decompositions and tractable queries. J. of Computer and System Sciences, 64(3), 579\u2013627.","journal-title":"J. of Computer and System Sciences"},{"key":"9362_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1613\/jair.3651","volume":"45","author":"DA Cohen","year":"2012","unstructured":"Cohen, D. A., Cooper, M. C., Creed, P., Marx, D., & Salamon, A. Z. (2012). The tractability of CSP classes defined by forbidden patterns. J. Artif. Intell. Res., 45, 47\u201378.","journal-title":"J. Artif. Intell. Res."},{"key":"9362_CR11","doi-asserted-by":"crossref","unstructured":"Cooper, M. .C., J\u00e9gou, P., & Terrioux, C. (2015). A microstructure-based family of tractable classes for CSPs. In G. Pesant (Ed.), Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings, Lecture Notes in Computer Science (Vol. 9255, pp. 74\u201388). Springer Verlag.","DOI":"10.1007\/978-3-319-23219-5_6"},{"key":"9362_CR12","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P.G., & Zivn\u00fd, S. (2015). Tractable classes of binary CSPs defined by excluded topological minors. In Q.\u00a0Yang, & M.\u00a0J. Wooldridge (Eds.), Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015 (pp. 1945\u20131951). AAAI Press."},{"key":"9362_CR13","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized Algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9362_CR14","doi-asserted-by":"crossref","unstructured":"Downey, R.G., & Fellows, M.R. (2013) Fundamentals of parameterized complexity. Texts in computer science. Springer Verlag.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"9362_CR15","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory, Texts in theoretical computer science. An EATCS series (vol. XIV). Berlin: Springer Verlag."},{"key":"9362_CR16","doi-asserted-by":"crossref","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford lecture series in mathematics and its applications. Oxford: Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"9362_CR17","doi-asserted-by":"publisher","unstructured":"Samer, M., & Szeider, S. (2021). Fixed-parameter tractability. In A. Biere, H. van Maaren, & T. Walsh (Eds.), Handbook of Satisfiability (2nd ed., Vol. 17, pp. 693\u2013736). IOS Press. https:\/\/doi.org\/10.3233\/FAIA201000.","DOI":"10.3233\/FAIA201000"},{"key":"9362_CR18","unstructured":"Williams, R., Gomes, C., & Selman, B. (2003). Backdoors to typical case complexity. In G.\u00a0Gottlob, & T.\u00a0Walsh (Eds.), Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003 (pp. 1173\u20131178). Morgan Kaufmann."},{"key":"9362_CR19","unstructured":"Williams, R., Gomes, C., & Selman, B. (2003). On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Informal Proc. of the Sixth International Conference on Theory and Applications of Satisfiability Testing, S. Margherita Ligure - Portofino, Italy, May 5-8, 2003 (pp. 222\u2013230). SAT."},{"key":"9362_CR20","unstructured":"Samer, M., Szeider, S. (2008). Backdoor trees. In AAAI 08, Twenty-Third Conference on Artificial Intelligence, Chicago, Illinois, July 13\u201317, 2008 (pp. 363\u2013368). AAAI Press."},{"key":"9362_CR21","doi-asserted-by":"publisher","unstructured":"Ordyniak, S., Schidler, A., & Szeider, S. (2021). Backdoor DNFs. In Z.\u00a0Zhou (Ed.), Proceeding of IJCAI-2021, the 30th International Joint Conference on Artificial Intelligence (pp. 1403\u20131409). https:\/\/doi.org\/10.24963\/ijcai.2021\/194.","DOI":"10.24963\/ijcai.2021\/194"},{"key":"9362_CR22","doi-asserted-by":"publisher","unstructured":"M\u00e4hlmann, N., Siebertz, S., & Vigny, A. (2021). Recursive backdoors for SAT. In F. Bonchi, & S. J. Puglisi (Eds.), 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, LIPIcs (Vol. 202, p. 73:1\u201373:18). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.73.","DOI":"10.4230\/LIPIcs.MFCS.2021.73"},{"issue":"6","key":"9362_CR23","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J Nesetril","year":"2006","unstructured":"Nesetril, J., & de Mendez, P. O. (2006). Tree-depth, subgraph coloring and homomorphism bounds. European J. Combin., 27(6), 1022\u20131041.","journal-title":"European J. Combin."},{"key":"9362_CR24","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., & de\u00a0Mendez, P.O. (2012). Sparsity - graphs, structures, and algorithms, algorithms and combinatorics (vol.\u00a028). Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"2","key":"9362_CR25","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00453-015-0045-3","volume":"75","author":"J Bulian","year":"2016","unstructured":"Bulian, J., & Dawar, A. (2016). Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica, 75(2), 363\u2013382.","journal-title":"Algorithmica"},{"key":"9362_CR26","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Golovach, P.A., & Thilikos, D.M. (2021). Parameterized complexity of elimination distance to first-order logic properties. arXiv:2104.02998.","DOI":"10.1109\/LICS52264.2021.9470540"},{"key":"9362_CR27","unstructured":"Dreier, J., Ordyniak, S., & Szeider, S. (2022). SAT backdoors: Depth beats size. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms, ESA 2022, LIPIcs, September 5-9, 2022, Berlin\/Potsdam, Germany (vol. 244, pp. 46:1\u201346:18). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik. arXiv:2202.08326."},{"key":"9362_CR28","doi-asserted-by":"publisher","unstructured":"Gaspers, S., Misra, N., Ordyniak, S., Szeider, S., & Zivny, S. (2017). Backdoors into heterogeneous classes of SAT and CSP. J. of Computer and System Sciences, 85, 38\u201356. https:\/\/doi.org\/10.1016\/j.jcss.2016.10.007.","DOI":"10.1016\/j.jcss.2016.10.007"},{"key":"9362_CR29","doi-asserted-by":"publisher","unstructured":"Ganian, R., Ramanujan, M. S., & Szeider, S. (2017). Discovering archipelagos of tractability for constraint satisfaction and counting. ACM Transactions on Algorithms, 13(2), 29:1\u201329:32. https:\/\/doi.org\/10.1145\/3014587.","DOI":"10.1145\/3014587"},{"key":"9362_CR30","doi-asserted-by":"publisher","unstructured":"Ganian, R., Ramanujan, M. .S., & Szeider, S. (2017). Combining treewidth and backdoors for CSP. In H. Vollmer, & B. Vall\u00e9e (Eds.), 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs) (Vol. 66, p. 36:1\u201336:17). Dagstuhl, Germany: Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2017.36.","DOI":"10.4230\/LIPIcs.STACS.2017.36"},{"key":"9362_CR31","unstructured":"Dreier, J., Ordyniak, S., & Szeider, S. (2022). CSP beyond tractable constraint languages. In C.\u00a0Solnon (Ed.), 28th International Conference on Principles and Practice of Constraint Programming, CP 2022, July 31\u2013 August 8, 2022, Haifa, Israel, LIPIcs (vol. 235, pp. 20:1\u201320:17). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"9362_CR32","doi-asserted-by":"publisher","unstructured":"Bulatov, A. A. (2011). Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4), 24:1\u201324:66. https:\/\/doi.org\/10.1145\/1970398.1970400.","DOI":"10.1145\/1970398.1970400"},{"key":"9362_CR33","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ramanujan, M.S., & Szeider, S. (2016). Discovering archipelagos of tractability for constraint satisfaction and counting. In R.\u00a0Krauthgamer (Ed.), Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 (pp. 1670\u20131681). SIAM.","DOI":"10.1137\/1.9781611974331.ch114"},{"key":"9362_CR34","doi-asserted-by":"publisher","unstructured":"Bulatov, A. A. (2013). The complexity of the counting constraint satisfaction problem. J. of the ACM, 60(5), 34:1\u201334:41. https:\/\/doi.org\/10.1145\/2528400.","DOI":"10.1145\/2528400"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09362-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10601-023-09362-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-023-09362-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T09:13:25Z","timestamp":1699521205000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10601-023-09362-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["9362"],"URL":"https:\/\/doi.org\/10.1007\/s10601-023-09362-3","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9]]},"assertion":[{"value":"29 August 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 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 financial or proprietary interests in any material discussed in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}