{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:37:18Z","timestamp":1753889838849,"version":"3.41.2"},"reference-count":32,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2012,3,26]],"date-time":"2012-03-26T00:00:00Z","timestamp":1332720000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>One of Courcelle's celebrated results states that if C is a class of graphs\nof bounded tree-width, then model-checking for monadic second order logic\n(MSO_2) is fixed-parameter tractable (fpt) on C by linear time parameterized\nalgorithms, where the parameter is the tree-width plus the size of the formula.\nAn immediate question is whether this is best possible or whether the result\ncan be extended to classes of unbounded tree-width. In this paper we show that\nin terms of tree-width, the theorem cannot be extended much further. More\nspecifically, we show that if C is a class of graphs which is closed under\ncolourings and satisfies certain constructibility conditions and is such that\nthe tree-width of C is not bounded by \\log^{84} n then MSO_2-model checking is\nnot fpt unless SAT can be solved in sub-exponential time. If the tree-width of\nC is not poly-logarithmically bounded, then MSO_2-model checking is not fpt\nunless all problems in the polynomial-time hierarchy can be solved in\nsub-exponential time.<\/jats:p>","DOI":"10.2168\/lmcs-8(1:27)2012","type":"journal-article","created":{"date-parts":[[2012,9,6]],"date-time":"2012-09-06T10:03:11Z","timestamp":1346925791000},"source":"Crossref","is-referenced-by-count":6,"title":["On the Parameterized Intractability of Monadic Second-Order Logic"],"prefix":"10.46298","volume":"Volume 8, Issue 1","author":[{"given":"Stephan","family":"Kreutzer","sequence":"first","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2012,3,26]]},"reference":[{"key":"10.2168\/LMCS-8(1:27)2012_BirmeleBonRee07","doi-asserted-by":"crossref","unstructured":"E. Birmel\u00e9, J. A. Bondy, and B. Reed. Brambles, prisms and grids. InGraph theory in Paris, Trends Math., pages 37-44. Birkh\u00e4user, 2007.","DOI":"10.1007\/978-3-7643-7400-6_4"},{"key":"10.2168\/LMCS-8(1:27)2012_BollobasTho98","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0188"},{"key":"10.2168\/LMCS-8(1:27)2012_Courcelle90","doi-asserted-by":"crossref","unstructured":"B. Courcelle. Graph rewriting: An algebraic and logic approach. In J. van Leeuwen, editor,Handbook of Theoretical Computer Science, volume 2, pages 194 - 242. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88074-1.50010-X"},{"key":"10.2168\/LMCS-8(1:27)2012_CourcelleMakRot00","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"10.2168\/LMCS-8(1:27)2012_CourcelleOumO07","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.04.003"},{"key":"10.2168\/LMCS-8(1:27)2012_DawarGroKre07","doi-asserted-by":"crossref","unstructured":"A. Dawar, M. Grohe, and S. Kreutzer. Locally excluding a minor. InLogic in Computer Science (LICS), pages 270-279, 2007.","DOI":"10.1109\/LICS.2007.31"},{"key":"10.2168\/LMCS-8(1:27)2012_Diestel05","doi-asserted-by":"crossref","unstructured":"R. Diestel.Graph Theory. Springer-Verlag, 3rd edition, 2005.","DOI":"10.1007\/978-3-642-14279-6_7"},{"key":"10.2168\/LMCS-8(1:27)2012_DowneyFel98","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows.Parameterized Complexity. Springer, 1998.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"10.2168\/LMCS-8(1:27)2012_EbbinghausFluTho94","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus, J. Flum, and W. Thomas.Mathematical Logic. Springer, 2nd edition, 1994.","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"10.2168\/LMCS-8(1:27)2012_FlumGro06","doi-asserted-by":"crossref","unstructured":"J. Flum and M. Grohe.Parameterized Complexity Theory. Springer, 2006. ISBN 3-54-029952-1.","DOI":"10.2168\/LMCS-1(1:2)2005"},{"key":"10.2168\/LMCS-8(1:27)2012_FlumGro01","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"10.2168\/LMCS-8(1:27)2012_FrickGro01","first-page":"1148","volume":"48","author":"M. Frick and M. Grohe","year":"2001","journal-title":"Journal of the ACM"},{"key":"10.2168\/LMCS-8(1:27)2012_GareyJohSto74","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"10.2168\/LMCS-8(1:27)2012_Grohe07","unstructured":"M. Grohe. Logic, graphs, and algorithms. In E.Gr\u00e4del T.Wilke J.Flum, editor,Logic and Automata - History and Perspectives. Amsterdam University Press, 2007."},{"key":"10.2168\/LMCS-8(1:27)2012_GroheK11","doi-asserted-by":"crossref","unstructured":"M. Grohe, and S. Kreutzer. Methods for Algorithmic Meta-Theorems. InModel Theoretic Methods in Finite Combinatorics,Contemporary Mathematics vol. 588, American Mathematical Society, 2011.","DOI":"10.1090\/conm\/558\/11051"},{"key":"10.2168\/LMCS-8(1:27)2012_GroheM09","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.06.004"},{"key":"10.2168\/LMCS-8(1:27)2012_Halin76","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"10.2168\/LMCS-8(1:27)2012_Hodges97","unstructured":"W. Hodges.A shorter model theory. Cambridge University Press, 1997."},{"key":"10.2168\/LMCS-8(1:27)2012_Kreutzer11","unstructured":"S. Kreutzer. Algorithmic meta-theorems. InFinite and Algorithmic Model Theory, London Mathematical Society Lecture Notes, No. 379, Cambridge University Press, 2011. See alsoElectronic Colloquium on Computational Complexity (ECCC)16: 147 (2009)"},{"key":"10.2168\/LMCS-8(1:27)2012_KreutzerTaz10b","doi-asserted-by":"crossref","unstructured":"S. Kreutzer and S. Tazari. Lower bounds for the complexity of monadic second-order logic. InLogic in Computer Science (LICS), 2010.","DOI":"10.1109\/LICS.2010.39"},{"key":"10.2168\/LMCS-8(1:27)2012_KreutzerTaz10","doi-asserted-by":"crossref","unstructured":"S. Kreutzer and S. Tazari. On brambles, grid-like minors, and parameterized intractability of monadic second-order logic. InSymposium on Discrete Algorithms (SODA), 2010.","DOI":"10.1137\/1.9781611973075.30"},{"key":"10.2168\/LMCS-8(1:27)2012_Mader67","doi-asserted-by":"publisher","DOI":"10.1007\/BF01364272"},{"issue":"303","key":"10.2168\/LMCS-8(1:27)2012_MakowskyM03","first-page":"157","volume":"1","author":"J. A. Makowsky and J. Mari\u00f1o","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"10.2168\/LMCS-8(1:27)2012_PapadimitriouY99","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"10.2168\/LMCS-8(1:27)2012_ReedWoo08","unstructured":"B. Reed and D. Wood. Polynomial treewidth forces a large grid-like minor. unpublished. Available at arXiv:0809.0724v3 [math.CO], 2008."},{"key":"10.2168\/LMCS-8(1:27)2012_RobertsonSeyTho94","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1073"},{"key":"10.2168\/LMCS-8(1:27)2012_GMV","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"10.2168\/LMCS-8(1:27)2012_GM-series","unstructured":"N. Robertson and P.D. Seymour. Graph minors I - XXIII, 1982 -. Appearing in Journal of Combinatorial Theory, Series B since 1982."},{"key":"10.2168\/LMCS-8(1:27)2012_Rose70","doi-asserted-by":"publisher","DOI":"10.1016\/0022-247X(70)90282-9"},{"key":"10.2168\/LMCS-8(1:27)2012_SeymourTho93","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"10.2168\/LMCS-8(1:27)2012_Thorup98","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"10.2168\/LMCS-8(1:27)2012_Vardi82","doi-asserted-by":"crossref","unstructured":"M. Vardi. On the complexity of relational query languages. InProc. of the 14th Symposium on Theory of Computing (STOC), pages 137-146, 1982.","DOI":"10.1145\/800070.802186"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/785\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/785\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:55:53Z","timestamp":1681242953000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,26]]},"references-count":32,"URL":"https:\/\/doi.org\/10.2168\/lmcs-8(1:27)2012","relation":{"is-same-as":[{"id-type":"arxiv","id":"1203.3167","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1203.3167","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2012,3,26]]},"article-number":"785"}}