{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T03:16:51Z","timestamp":1773803811199,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T00:00:00Z","timestamp":1497571200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme","award":["648527"],"award-info":[{"award-number":["648527"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>Nowhere dense graph classes, introduced by Ne\u0161et\u0159il and Ossona de Mendez [2010, 2011], form a large variety of classes of \u201csparse graphs\u201d including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion.<\/jats:p>\n          <jats:p>\n            We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes (parameterized by the length of the input formula). At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes\n            <jats:italic>C<\/jats:italic>\n            of graphs closed under taking subgraphs, if deciding first-order properties of graphs in\n            <jats:italic>C<\/jats:italic>\n            is fixed-parameter tractable, then\n            <jats:italic>C<\/jats:italic>\n            must be nowhere dense (under a reasonable complexity theoretic assumption).\n          <\/jats:p>\n          <jats:p>As a by-product, we give an algorithmic construction of sparse neighborhood covers for nowhere dense graphs. This extends and improves previous constructions of neighborhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those.<\/jats:p>\n          <jats:p>Our proofs are based on a new game-theoretic characterization of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a \u201crank-preserving\u201d version of Gaifman\u2019s locality theorem.<\/jats:p>","DOI":"10.1145\/3051095","type":"journal-article","created":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T18:10:59Z","timestamp":1497636659000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Deciding First-Order Properties of Nowhere Dense Graphs"],"prefix":"10.1145","volume":"64","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0292-9142","authenticated-orcid":false,"given":"Martin","family":"Grohe","sequence":"first","affiliation":[{"name":"RWTH Aachen University, Aachen, Germany"}]},{"given":"Stephan","family":"Kreutzer","sequence":"additional","affiliation":[{"name":"Technical University Berlin, Berlin, Germany"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"Technical University Berlin, Berlin, Germany"}]}],"member":"320","published-online":{"date-parts":[[2017,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248381"},{"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\/1281100.1281112"},{"key":"e_1_2_1_4_1","volume-title":"Handbook of Theoretical Computer Science","author":"Courcelle B.","unstructured":"B. Courcelle . 1990. Graph rewriting: An algebraic and logic approach . In Handbook of Theoretical Computer Science , J. van Leeuwen (Ed.). Vol. B. Elsevier Science, 194-- 242 . B. Courcelle. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, J. van Leeuwen (Ed.). Vol. B. Elsevier Science, 194--242."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00221-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.10.005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.13"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909)","author":"Dawar A.","unstructured":"A. Dawar and S. Kreutzer . 2009. Domination problems in nowhere-dense classes of graphs . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909) . 157--168. A. Dawar and S. Kreutzer. 2009. Domination problems in nowhere-dense classes of graphs. In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909). 157--168."},{"key":"e_1_2_1_11_1","volume-title":"Graph Theory","author":"Diestel R.","unstructured":"R. Diestel . 2005. Graph Theory ( 3 rd ed.). Springer-Verlag . R. Diestel. 2005. Graph Theory (3rd ed.). Springer-Verlag.","edition":"3"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"R. Downey and M. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.   R. Downey and M. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"e_1_2_1_13_1","volume-title":"Witten (Eds.)","volume":"39","author":"Downey R. G.","unstructured":"R. G. Downey , M. R. Fellows , and U. Taylor . 1996. The parameterized complexity of relational database queries and an improved characterization of W{1}. In Combinatorics, Complexity, and Logic, C. Calude, P. Gibbons, S. Reeves, and I. H . Witten (Eds.) , Vol. 39 . Springer-Verlag, 194--213. R. G. Downey, M. R. Fellows, and U. Taylor. 1996. The parameterized complexity of relational database queries and an improved characterization of W{1}. In Combinatorics, Complexity, and Logic, C. Calude, P. Gibbons, S. Reeves, and I. H. Witten (Eds.), Vol. 39. Springer-Verlag, 194--213."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2012.12.004"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.20"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus J. Flum and W. Thomas. 1994. Mathematical Logic (2nd ed.). Springer.  H.-D. Ebbinghaus J. Flum and W. Thomas. 1994. Mathematical Logic (2nd ed.). Springer.","DOI":"10.1007\/978-1-4757-2355-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.21"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591865"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_2_1_21_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag.   J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag."},{"key":"e_1_2_1_22_1","volume-title":"Sur quelques classifications des systemes de relations","author":"Fra\u00efss\u00e9 R.","unstructured":"R. Fra\u00efss\u00e9 . 1954. Sur quelques classifications des systemes de relations . Publications scientifiques de l\u2019Universite d\u2019Alger, Series A, Sciences mathematiques, 35--182. R. Fra\u00efss\u00e9. 1954. Sur quelques classifications des systemes de relations. Publications scientifiques de l\u2019Universite d\u2019Alger, Series A, Sciences mathematiques, 35--182."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"J. Gajarsk\u00fd P. Hlinen\u00fd D. Lokshtanov J. Obdrz\u00e1lek S. Ordyniak M. S. Ramanujan and S. Saurabh. 2015. FO model checking on posets of bounded width. arXiv:1504.04115v2{cs.LO}.  J. Gajarsk\u00fd P. Hlinen\u00fd D. Lokshtanov J. Obdrz\u00e1lek S. Ordyniak M. S. Ramanujan and S. Saurabh. 2015. FO model checking on posets of bounded width. arXiv:1504.04115v2{cs.LO}.","DOI":"10.1109\/FOCS.2015.63"},{"key":"e_1_2_1_26_1","volume-title":"Logic and Automata\u2014History and Perspectives (Texts in Logic and Games)","author":"Grohe M.","unstructured":"M. Grohe . 2007. Logic, graphs, and algorithms . In Logic and Automata\u2014History and Perspectives (Texts in Logic and Games) , J. Flum, E. Gr\u00e4del, and T. Wilke (Eds.), Vol. 2 . Amsterdam University Press , Amsterdam, Netherlands , 357--422. M. Grohe. 2007. Logic, graphs, and algorithms. In Logic and Automata\u2014History and Perspectives (Texts in Logic and Games), J. Flum, E. Gr\u00e4del, and T. Wilke (Eds.), Vol. 2. Amsterdam University Press, Amsterdam, Netherlands, 357--422."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06686-8_2"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms.","author":"Grohe M.","unstructured":"M. Grohe , K. Kawarabayashi , and B. Reed . 2013. A simple algorithm for the graph minor decomposition: Logic meets structural graph theory . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. M. Grohe, K. Kawarabayashi, and B. Reed. 2013. A simple algorithm for the graph minor decomposition: Logic meets structural graph theory. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_29_1","volume-title":"Contemporary Mathematics","volume":"558","author":"Grohe M.","unstructured":"M. Grohe and S. Kreutzer . 2011. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics, M. Grohe and J.A. Makowsky (Eds.) . Contemporary Mathematics , Vol. 558 . American Mathematical Society, 181--206. M. Grohe and S. Kreutzer. 2011. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics, M. Grohe and J.A. Makowsky (Eds.). Contemporary Mathematics, Vol. 558. American Mathematical Society, 181--206."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53174-7_23"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:ORDE.0000026489.93166.cb"},{"key":"e_1_2_1_32_1","volume-title":"Cambridge University Press","author":"Kreutzer S.","unstructured":"S. Kreutzer . 2011. Algorithmic meta-theorems . In Finite and Algorithmic Model Theory, J. Esparza, C. Michaux, and C. Steinhorn (Eds.). Cambridge University Press , Cambridge , England , 177--270. S. Kreutzer. 2011. Algorithmic meta-theorems. In Finite and Algorithmic Model Theory, J. Esparza, C. Michaux, and C. Steinhorn (Eds.). Cambridge University Press, Cambridge, England, 177--270."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2010.39"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. 354--364","author":"Kreutzer S.","unstructured":"S. Kreutzer and S. Tazari . 2010b. On brambles, grid-like minors, and parameterized intractability of monadic second-order logic . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. 354--364 . S. Kreutzer and S. Tazari. 2010b. On brambles, grid-like minors, and parameterized intractability of monadic second-order logic. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms. 354--364."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX\u201912)","author":"Langer A.","unstructured":"A. Langer , F. Reidl , P. Rossmanith , and S. Sikdar . 2012. Evaluation of an MSO-solver . In Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX\u201912) . 55--63. A. Langer, F. Reidl, P. Rossmanith, and S. Sikdar. 2012. Evaluation of an MSO-solver. In Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX\u201912). 55--63."},{"key":"e_1_2_1_36_1","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez. 2005. Grad and classes with bounded expansion II. Algorithmic aspects. arXiv:math\/0508324v2.  J. Ne\u0161et\u0159il and P. Ossona de Mendez. 2005. Grad and classes with bounded expansion II. Algorithmic aspects. arXiv:math\/0508324v2."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1278682204"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_2_1_39_1","volume-title":"Algorithms and Combinatorics","author":"Ne\u0161et\u0159il J.","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez . 2012. Sparsity. Algorithms and Combinatorics , Vol. 28 . Springer , 61--88. J. Ne\u0161et\u0159il and P. Ossona de Mendez. 2012. Sparsity. Algorithms and Combinatorics, Vol. 28. Springer, 61--88."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051095","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3051095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:38Z","timestamp":1750222478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,16]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3051095"],"URL":"https:\/\/doi.org\/10.1145\/3051095","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,16]]},"assertion":[{"value":"2015-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}