{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:48:38Z","timestamp":1742914118131,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642415234"},{"type":"electronic","value":"9783642415241"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-642-41524-1_2","type":"book-chapter","created":{"date-parts":[[2013,11,15]],"date-time":"2013-11-15T10:48:20Z","timestamp":1384512500000},"page":"27-37","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Parameterized Complexity of Constraint Satisfaction and Reasoning"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Szeider","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,11,16]]},"reference":[{"key":"2_CR1","first-page":"279","volume-title":"ICALP 2007. LNCS","author":"A Atserias","year":"2007","unstructured":"Atserias, A., Bulatov, A., Dalmau, V.: On the power of k-consistency. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 279\u2013290. Springer, Heidelberg (2007)"},{"key":"2_CR2","first-page":"318","volume-title":"Fellows Festschrift 2012. LNCS","author":"N Betzler","year":"2012","unstructured":"Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in computational aspects of voting- a parameterized complexity perspective. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 318\u2013363. Springer, Heidelberg (2012)"},{"key":"2_CR3","first-page":"193","volume-title":"TACAS 1999. LNCS","author":"A Biere","year":"1999","unstructured":"Biere, A., Cimatti, A., Clarke, E., Zhu, Y.: Symbolic model checking without BDDs. TACAS 1999. LNCS, vol. 1579, pp. 193\u2013207. Springer, Heidelberg (1999)"},{"key":"2_CR4","first-page":"563","volume-title":"ICALP 2008, Part I. LNCS","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"2_CR5","first-page":"93","volume-title":"SWAT 2010. LNCS","author":"Y Cao","year":"2010","unstructured":"Cao, Y., Chen, J., Liu, Y.: On feedback vertex set new measure and new structures. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 93\u2013104. Springer, Heidelberg (2010)"},{"issue":"40\u201342","key":"2_CR6","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoret. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"2_CR7","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1093\/comjnl\/bxm036","volume":"51","author":"J Chen","year":"2008","unstructured":"Chen, J., Meng, J.: On parameterized intractability: hardness and completeness. Comput. J. 51(1), 39\u201359 (2008)","journal-title":"Comput. J."},{"key":"2_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity. Monographs in Computer Science","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"issue":"10\u201315","key":"2_CR9","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/j.artint.2007.03.006","volume":"171","author":"PE Dunne","year":"2007","unstructured":"Dunne, P.E.: Computational properties of argument systems satisfying graph-theoretic constraints. Artif. Intell. 171(10\u201315), 701\u2013729 (2007)","journal-title":"Artif. Intell."},{"key":"2_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/j.artint.2012.03.002","volume":"186","author":"W Dvor\u00e1k","year":"2012","unstructured":"Dvor\u00e1k, W., Ordyniak, S., Szeider, S.: Augmenting tractable fragments of abstract argumentation. Artif. Intell. 186, 157\u2013173 (2012)","journal-title":"Artif. Intell."},{"issue":"3\u20134","key":"2_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/BF01536399","volume":"15","author":"T Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: On the computational cost of disjunctive logic programming: propositional case. Ann. Math. Artif. Intell. 15(3\u20134), 289\u2013323 (1995)","journal-title":"Ann. Math. Artif. Intell."},{"key":"2_CR12","first-page":"276","volume-title":"IWPEC 2006. LNCS","author":"MR Fellows","year":"2006","unstructured":"Fellows, M.R.: The lost continent of polynomial time: preprocessing and kernelization. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 276\u2013277. Springer, Heidelberg (2006)"},{"key":"2_CR13","unstructured":"Fichte, J.K., Szeider, S.: Backdoors to tractable answer-set programming. Technical Report 1104.2788, Arxiv.org. Extended and updated version of a paper that appeared in the proceedings of IJCAI 2011, The 22nd International Joint Conference on Artificial Intelligence (2012)"},{"key":"2_CR14","first-page":"320","volume-title":"Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013), Bellevue, Washington, USA, 14\u201318 July 2013","author":"JK Fichte","year":"2013","unstructured":"Fichte, J.K., Szeider, S.: Backdoors to normality for disjunctive logic programs. In: des Jardins, M., Littman, M.L. (eds.) Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI 2013), Bellevue, Washington, USA, 14\u201318 July 2013, pp. 320\u2013337. AAAI Press, California (2013)"},{"key":"2_CR15","volume-title":"Parameterized Complexity Theory, vol. XIV. Texts in Theoretical Computer Science. An EATCS Series","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory, vol. XIV. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2006)"},{"key":"2_CR16","first-page":"133","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 17\u201320 May 2008","author":"L Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, 17\u201320 May 2008, pp. 133\u2013142. ACM, New York (2008)"},{"issue":"11","key":"2_CR17","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1145\/359642.359654","volume":"21","author":"EC Freuder","year":"1978","unstructured":"Freuder, E.C.: Synthesizing constraint expressions. Commun. ACM 21(11), 958\u2013966 (1978)","journal-title":"Commun. ACM"},{"issue":"4","key":"2_CR18","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1145\/4221.4225","volume":"32","author":"EC Freuder","year":"1985","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-bounded search. J. ACM 32(4), 755\u2013761 (1985)","journal-title":"J. ACM"},{"key":"2_CR19","first-page":"540","volume-title":"Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011","author":"S Gaspers","year":"2011","unstructured":"Gaspers, S., Szeider, S.: Kernels for global constraints. In: Walsh, T. (ed.) Proceedings of the 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, pp. 540\u2013545. AAAI Press, California (2011)"},{"key":"2_CR20","first-page":"302","volume-title":"CP 2011. LNCS","author":"S Gaspers","year":"2011","unstructured":"Gaspers, S., Szeider, S.: The parameterized complexity of local consistency. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 302\u2013316. Springer, Heidelberg (2011)"},{"key":"2_CR21","first-page":"287","volume-title":"Fellows Festschrift 2012. LNCS","author":"S Gaspers","year":"2012","unstructured":"Gaspers, S., Szeider, S.: Backdoors to satisfaction. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 287\u2013317. Springer, Heidelberg (2012)"},{"issue":"3","key":"2_CR22","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1093\/comjnl\/bxm053","volume":"51","author":"P Giannopoulos","year":"2008","unstructured":"Giannopoulos, P., Knauer, C., Whitesides, S.: Parameterized complexity of geometric problems. Comput. J. 51(3), 372\u2013384 (2008)","journal-title":"Comput. J."},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1574-6526(07)03002-7","volume-title":"Handbook of Knowledge Representation, vol. 3, Foundations of Artificial Intelligence","author":"CP Gomes","year":"2008","unstructured":"Gomes, C.P., Kautz, H., Sabharwal, A., Selman, B.: Satisfiability solvers. In: van Harmelen, F., Lifschitz, V. (eds.) Handbook of Knowledge Representation, vol. 3, Foundations of Artificial Intelligence, pp. 89\u2013134. Elsevier, Amsterdam (2008)"},{"key":"2_CR24","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Bounded treewidth as a key to tractability of knowledge representation and reasoning. In: 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference. AAAI Press (2006)"},{"key":"2_CR25","unstructured":"Gottlob, G., Pichler, R., Wei, F.: Abduction with bounded treewidth: from theoretical tractability to practically efficient computation. In: Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence (AAAI 2008), Chicago, Illinois, USA, 13\u201317 July 2008, pp. 1541\u20131546. AAAI Press, California (2008)"},{"issue":"1","key":"2_CR26","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1093\/comjnl\/bxm049","volume":"51","author":"J Gramm","year":"2008","unstructured":"Gramm, J., Nickelsen, A., Tantau, T.: Fixed-parameter algorithms in phylogenetics. Comput. J. 51(1), 79\u2013101 (2008)","journal-title":"Comput. J."},{"key":"2_CR27","first-page":"257","volume-title":"Fellows Festschrift 2012. LNCS","author":"G Gutin","year":"2012","unstructured":"Gutin, G., Yeo, A.: Constraint satisfaction problems parameterized above or below tight bounds: a survey. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 257\u2013286. Springer, Heidelberg (2012)"},{"issue":"3","key":"2_CR28","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P Hlinen\u00fd","year":"2008","unstructured":"Hlinen\u00fd, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326\u2013362 (2008)","journal-title":"Comput. J."},{"issue":"4","key":"2_CR29","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"1722","DOI":"10.1016\/j.artint.2011.03.001","volume":"175","author":"EJ Kim","year":"2011","unstructured":"Kim, E.J., Ordyniak, S., Szeider, S.: Algorithms and complexity results for persuasive argumentation. Artif. Intell. 175, 1722\u20131736 (2011)","journal-title":"Artif. Intell."},{"issue":"2","key":"2_CR31","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/2151171.2151182","volume":"8","author":"A Krokhin","year":"2012","unstructured":"Krokhin, A., Marx, D.: On the hardness of losing weight. ACM Trans. Algorithm 8(2), 19 (2012)","journal-title":"ACM Trans. Algorithm"},{"key":"2_CR32","first-page":"129","volume-title":"Fellows Festschrift 2012. LNCS","author":"D Lokshtanov","year":"2012","unstructured":"Lokshtanov, D., Misra, N., Saurabh, S.: Kernelization \u2013 preprocessing with a guarantee. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 129\u2013161. Springer, Heidelberg (2012)"},{"key":"2_CR33","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.: Consistency in networks of relations. Artif. Intell. 8, 99\u2013118 (1977)","journal-title":"Artif. Intell."},{"issue":"2","key":"2_CR34","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. J. Algorithms 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"key":"2_CR35","first-page":"38","volume-title":"IWPEC 2006. LNCS","author":"M Mahajan","year":"2006","unstructured":"Mahajan, M., Raman, V., Sikdar, S.: Parameterizing MAX SNP problems above guaranteed values. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 38\u201349. Springer, Heidelberg (2006)"},{"key":"2_CR36","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95\u2013132 (1974)","journal-title":"Inf. Sci."},{"key":"2_CR37","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford (2006)"},{"issue":"7\u20138","key":"2_CR38","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/s00236-007-0056-x","volume":"44","author":"N Nishimura","year":"2007","unstructured":"Nishimura, N., Ragde, P., Szeider, S.: Solving #SAT using vertex covers. Acta Informatica 44(7\u20138), 509\u2013523 (2007)","journal-title":"Acta Informatica"},{"key":"2_CR39","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.tcs.2012.12.039","volume":"481","author":"S Ordyniak","year":"2013","unstructured":"Ordyniak, S., Paulusma, D., Szeider, S.: Satisfiability of acyclic and almost acyclic cnf formulas. Theor. Comput. Sci. 481, 85\u201399 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"2_CR40","unstructured":"Pfandler, A., R\u00fcmmele, S., Szeider, S.: Backdoors to absuction. In: Proceedings of the 23th International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China, 3\u20139 August 2013 (2013) (to appear)"},{"key":"2_CR41","volume-title":"Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference (KR 2010), Toronto, Ontario, Canada, 9\u201313 May 2010","author":"R Pichler","year":"2010","unstructured":"Pichler, R., R\u00fcmmele, S., Szeider, S., Woltran, S.: Tractable answer-set programming with weight constraints: bounded treewidth is not enough. In: Lin, F., Sattler, U., Truszczynski, M. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference (KR 2010), Toronto, Ontario, Canada, 9\u201313 May 2010. AAAI Press, California (2010)"},{"issue":"1","key":"2_CR42","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/s10817-008-9114-5","volume":"42","author":"M Samer","year":"2009","unstructured":"Samer, M., Szeider, S.: Backdoor sets of quantified Boolean formulas. J. Autom. Reason. 42(1), 77\u201397 (2009)","journal-title":"J. Autom. Reason."},{"issue":"1","key":"2_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10601-009-9079-y","volume":"16","author":"M Samer","year":"2009","unstructured":"Samer, M., Szeider, S.: Tractable cases of the extended global cardinality constraint. Constraints 16(1), 1\u201324 (2009)","journal-title":"Constraints"},{"issue":"1","key":"2_CR44","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1016\/j.jda.2009.06.002","volume":"8","author":"M Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Algorithms for propositional model counting. J. Discret. Algorithms 8(1), 50\u201364 (2010)","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"2_CR45","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.jcss.2009.04.003","volume":"76","author":"M Samer","year":"2010","unstructured":"Samer, M., Szeider, S.: Constraint satisfaction with bounded treewidth revisited. J. Comput. Syst. Sci. 76(2), 103\u2013114 (2010)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"2_CR46","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1093\/comjnl\/bxm038","volume":"51","author":"C Sloper","year":"2008","unstructured":"Sloper, C., Telle, J.A.: An overview of techniques for designing parameterized algorithms. Comput. J. 51(1), 122\u2013136 (2008)","journal-title":"Comput. J."},{"key":"2_CR47","first-page":"93","volume-title":"Proceedings of the twenty-fifth conference on artificial intelligence, AAAI 2011","author":"S Szeider","year":"2011","unstructured":"Szeider, S.: Limits of preprocessing. Proceedings of the twenty-fifth conference on artificial intelligence, AAAI 2011, pp. 93\u201398. AAAI Press, California (2011)"},{"issue":"1","key":"2_CR48","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.disopt.2010.07.003","volume":"8","author":"S Szeider","year":"2011","unstructured":"Szeider, S.: The parameterized complexity of $$k$$-flip local search for SAT and MAX SAT. Discrete Optim. 8(1), 139\u2013145 (2011)","journal-title":"Discrete Optim."},{"key":"2_CR49","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: On P, NP, and computational complexity. Commun. ACM 53(11), 5 (Nov. 2010)","DOI":"10.1145\/1839676.1839677"},{"key":"2_CR50","first-page":"1173","volume-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003","author":"R Williams","year":"2003","unstructured":"Williams, R., Gomes, C., Selman, B.: Backdoors to typical case complexity. In: Gottlob, G., Walsh, T. (eds.) Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI 2003, pp. 1173\u20131178. Morgan Kaufmann, San Francisco (2003)"}],"container-title":["Lecture Notes in Computer Science","Applications of Declarative Programming and Knowledge Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-41524-1_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:13:31Z","timestamp":1674227611000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-41524-1_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642415234","9783642415241"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-41524-1_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]},"assertion":[{"value":"16 November 2013","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}