{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T06:58:27Z","timestamp":1760079507980,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["239962"],"award-info":[{"award-number":["239962"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>\n            We introduce the class of MSO-LCC problems, which are problems of the following form. Given a graph\n            <jats:italic>G<\/jats:italic>\n            and for each vertex\n            <jats:italic>v<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            a set \u03b1(\n            <jats:italic>v<\/jats:italic>\n            ) of non-negative integers. Is there a set\n            <jats:italic>S<\/jats:italic>\n            of vertices or edges of\n            <jats:italic>G<\/jats:italic>\n            such that, (1)\n            <jats:italic>S<\/jats:italic>\n            satisfies a fixed property expressible in monadic second order logic, and (2) for each vertex\n            <jats:italic>v<\/jats:italic>\n            of\n            <jats:italic>G<\/jats:italic>\n            the number of vertices\/edges in\n            <jats:italic>S<\/jats:italic>\n            adjacent\/incident with\n            <jats:italic>v<\/jats:italic>\n            belongs to the set \u03b1(\n            <jats:italic>v<\/jats:italic>\n            )? We demonstrate that several hard combinatorial problems such as Lov\u00e1sz's General Factor Problem can be naturally formulated as MSO-LCC problems. Our main result is the polynomial-time tractability of MSO-LCC problems for graphs of bounded treewidth. We obtain this result by means of a tree-automata approach. By way of contrast we show that a more general class of MSO-LCC problems, where cardinality constraints are applied to second-order variables that are arbitrarily quantified, does not admit polynomial-time tractability for graphs of bounded treewidth unless P=NP.\n          <\/jats:p>","DOI":"10.1145\/1877714.1877718","type":"journal-article","created":{"date-parts":[[2011,1,25]],"date-time":"2011-01-25T19:12:52Z","timestamp":1295982772000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Monadic second order logic on graphs with local cardinality constraints"],"prefix":"10.1145","volume":"12","author":[{"given":"Stefan","family":"Szeider","sequence":"first","affiliation":[{"name":"Vienna University of Technology, Vienna, Austria"}]}],"member":"320","published-online":{"date-parts":[[2011,1,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"volume":"77","volume-title":"Proceedings of Computing: The Australasian Theory Symposium (CATS). J. Harland and P. Manyem, Eds., Conferences in Research and Practice in Information Technology","author":"Asahiro Y.","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.027"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(88)90068-8"},{"key":"e_1_2_1_8_1","unstructured":"Courcelle B. 1987. Recognizability and second-order definability for sets of finite graphs. Tech. rep. I-8634 Universit\u00e9 de Bordeaux.  Courcelle B. 1987. Recognizability and second-order definability for sets of finite graphs. Tech. rep. I-8634 Universit\u00e9 de Bordeaux."},{"volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Monographs in Computer Science. Springer-Verlag Berlin.  Downey R. G. and Fellows M. R. 1999. Parameterized Complexity. Monographs in Computer Science. Springer-Verlag Berlin.","DOI":"10.1007\/978-1-4612-0515-9"},{"volume-title":"An EATCS Series","author":"Flum J.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(04)00081-8"},{"key":"e_1_2_1_13_1","unstructured":"Garey M. R. and Johnson D. R. 1979. Computers and Intractability. W. H. Freeman and Company New York.   Garey M. R. and Johnson D. R. 1979. Computers and Intractability. W. H. Freeman and Company New York."},{"volume-title":"Logic and Automata: History and Perspectives","author":"Grohe M.","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103436505"},{"volume-title":"Handbook of Combinatorial Optimization","author":"Lih K.-W.","key":"e_1_2_1_17_1"},{"volume-title":"Combinatorial Structures and their Applications (Proceedings of the Calgary International Conformation). Gordon and Breach","author":"Lov\u00e1sz L.","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01889919"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1973.11993408"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press Oxford.  Niedermeier R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford University Press Oxford.","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90042-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10601-009-9079-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1952-028-2"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1877714.1877718","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1877714.1877718","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:17:37Z","timestamp":1750249057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1877714.1877718"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1145\/1877714.1877718"],"URL":"https:\/\/doi.org\/10.1145\/1877714.1877718","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2011,1]]},"assertion":[{"value":"2009-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-01-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}