{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T14:00:03Z","timestamp":1779890403381,"version":"3.53.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,3,6]],"date-time":"2017-03-06T00:00:00Z","timestamp":1488758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"FWF","award":["P26696"],"award-info":[{"award-number":["P26696"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,4,30]]},"abstract":"<jats:p>\n            The Constraint Satisfaction Problem (CSP) is a central and generic computational problem which provides a common framework for many theoretical and practical applications. A central line of research is concerned with the identification of classes of instances for which CSP can be solved in polynomial time; such classes are often called \u201cislands of tractability.\u201d A prominent way of defining islands of tractability for CSP is to restrict the relations that may occur in the constraints to a fixed set, called a\n            <jats:italic>constraint language<\/jats:italic>\n            , whereas a constraint language is conservative if it contains all unary relations. Schaefer\u2019s famous Dichotomy Theorem (STOC 1978) identifies all islands of tractability in terms of tractable constraint languages over a Boolean domain of values. Since then, many extensions and generalizations of this result have been obtained. Recently, Bulatov (TOCL 2011, JACM 2013) gave a full characterization of all islands of tractability for CSP and the counting version #CSP that are defined in terms of conservative constraint languages.\n          <\/jats:p>\n          <jats:p>\n            This article addresses the general limit of the mentioned tractability results for CSP and #CSP, that they only apply to instances where all constraints belong to a single tractable language (in general, the union of two tractable languages is not tractable). We show that we can overcome this limitation as long as we keep some control of how constraints over the various considered tractable languages interact with each other. For this purpose, we utilize the notion of a\n            <jats:italic>strong backdoor<\/jats:italic>\n            of a CSP instance, as introduced by Williams et al. (IJCAI 2003), which is a set of variables that when instantiated, moves the instance to an island of tractability, that is, to a tractable class of instances. We consider strong backdoors into\n            <jats:italic>scattered classes<\/jats:italic>\n            , consisting of CSP instances where each connected component belongs entirely to some class from a list of tractable classes. Figuratively speaking, a scattered class constitutes an\n            <jats:italic>archipelago of tractability<\/jats:italic>\n            . The main difficulty lies in finding a strong backdoor of given size\n            <jats:italic>k<\/jats:italic>\n            ; once it is found, we can try all possible instantiations of the backdoor variables and apply the polynomial time algorithms associated with the islands of tractability on the list component-wise. Our main result is an algorithm that, given a CSP instance with\n            <jats:italic>n<\/jats:italic>\n            variables, finds in time\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            a strong backdoor into a scattered class (associated with a list of finite conservative constraint languages) of size\n            <jats:italic>k<\/jats:italic>\n            or correctly decides that there is not such a backdoor. This also gives the running time for solving (#)CSP, provided that (#)CSP is polynomial-time tractable for the considered constraint languages. Our result makes significant progress towards the main goal of the backdoor-based approach to CSPs\u2014the identification of maximal base classes for which small backdoors can be detected efficiently.\n          <\/jats:p>","DOI":"10.1145\/3014587","type":"journal-article","created":{"date-parts":[[2017,3,7]],"date-time":"2017-03-07T19:12:04Z","timestamp":1488913924000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting"],"prefix":"10.1145","volume":"13","author":[{"given":"Robert","family":"Ganian","sequence":"first","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,3,6]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Francesca Rossi (Ed.). IJCAI\/AAAI.","author":"Bessiere Christian","year":"2013","unstructured":"Christian Bessiere , Cl\u00e9ment Carbonnel , Emmanuel Hebrard , George Katsirelos , and Toby Walsh . 2013 . Detecting and exploiting subproblem tractability . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Francesca Rossi (Ed.). IJCAI\/AAAI. Christian Bessiere, Cl\u00e9ment Carbonnel, Emmanuel Hebrard, George Katsirelos, and Toby Walsh. 2013. Detecting and exploiting subproblem tractability. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Francesca Rossi (Ed.). IJCAI\/AAAI."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1747997"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120582.1120584"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2528400"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.09.005"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10428-7_18"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9130-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90021-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00028-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1087"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0016"},{"key":"e_1_2_1_14_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_15_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2012. Graph Theory , 4 th Edition. Graduate texts in mathematics, Vol. 173 . Springer . Reinhard Diestel. 2012. Graph Theory, 4th Edition. Graduate texts in mathematics, Vol. 173. Springer.","edition":"4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer Verlag New York.   R. G. Downey and M. R. Fellows. 1999. Parameterized Complexity. Springer Verlag New York.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"e_1_2_1_17_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167245"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_20_1","series-title":"An EATCS Series","volume-title":"Parameterized Complexity Theory. Texts in Theoretical Computer Science","author":"Flum J\u00f6rg","unstructured":"J\u00f6rg Flum and Martin Grohe . 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science . An EATCS Series , Vol. XIV . Springer Verlag , Berlin . J\u00f6rg Flum and Martin Grohe. 2006. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Vol. XIV. Springer Verlag, Berlin."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722172"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 28th AAAI Conference on Artificial Intelligence, Carla E. Brodley and Peter Stone (Eds.). AAAI Press, 2652--2658","author":"Gaspers Serge","year":"2014","unstructured":"Serge Gaspers , Neeldhara Misra , Sebastian Ordyniak , Stefan Szeider , and Stanislav Zivny . 2014 . Backdoors into heterogeneous classes of SAT and CSP . In Proceedings of the 28th AAAI Conference on Artificial Intelligence, Carla E. Brodley and Peter Stone (Eds.). AAAI Press, 2652--2658 . Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, and Stanislav Zivny. 2014. Backdoors into heterogeneous classes of SAT and CSP. In Proceedings of the 28th AAAI Conference on Artificial Intelligence, Carla E. Brodley and Peter Stone (Eds.). AAAI Press, 2652--2658."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","volume":"20","author":"Gaspers Serge","year":"2013","unstructured":"Serge Gaspers , Sebastian Ordyniak , M. S. Ramanujan , Saket Saurabh , and Stefan Szeider . 2013 . Backdoors to q-Horn . In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913) , Natacha Portier and Thomas Wilke (Eds.) , Vol. 20 . Leibniz-Zentrum fuer Informatik, 67--79. Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider. 2013. Backdoors to q-Horn. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913), Natacha Portier and Thomas Wilke (Eds.), Vol. 20. Leibniz-Zentrum fuer Informatik, 67--79."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.59"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/07070440X"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2421119.2421135"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1630659.1630939"},{"key":"e_1_2_1_30_1","volume-title":"Vardi","author":"Kolaitis Phokion G.","year":"2007","unstructured":"Phokion G. Kolaitis and Moshe Y . Vardi . 2007 . A logical approach to constraint satisfaction. In Finite Model Theory and its Applications. Springer Verlag , 339--370. Phokion G. Kolaitis and Moshe Y. Vardi. 2007. A logical approach to constraint satisfaction. In Finite Model Theory and its Applications. Springer Verlag, 339--370."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450146"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_63"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.007"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of 7th International Conference on Theory and Applications of Satisfiability Testing. 96--103","author":"Nishimura Naomi","year":"2004","unstructured":"Naomi Nishimura , Prabhakar Ragde , and Stefan Szeider . 2004 . Detecting backdoor sets with respect to horn and binary clauses . In Proceedings of 7th International Conference on Theory and Applications of Satisfiability Testing. 96--103 . Naomi Nishimura, Prabhakar Ragde, and Stefan Szeider. 2004. Detecting backdoor sets with respect to horn and binary clauses. In Proceedings of 7th International Conference on Theory and Applications of Satisfiability Testing. 96--103."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.002"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2003.10.009"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804350"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488697"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1630659.1630827"},{"key":"e_1_2_1_42_1","volume-title":"Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903)","author":"Williams Ryan","year":"2003","unstructured":"Ryan Williams , Carla Gomes , and Bart Selman . 2003 b. On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search . In Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903) . 222--230. Ryan Williams, Carla Gomes, and Bart Selman. 2003b. On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search. In Informal Proceedings of the 6th International Conference on Theory and Applications of Satisfiability Testing (SAT\u201903). 222--230."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3014587","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3014587","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:59Z","timestamp":1750273499000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3014587"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,6]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,4,30]]}},"alternative-id":["10.1145\/3014587"],"URL":"https:\/\/doi.org\/10.1145\/3014587","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,3,6]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}