{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:12Z","timestamp":1781078172559,"version":"3.54.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,5]],"date-time":"2020-07-05T00:00:00Z","timestamp":1593907200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Pareto-Optimal Parameterized Algorithms, ERC Starting","award":["715744"],"award-info":[{"award-number":["715744"]}]},{"DOI":"10.13039\/501100006475","name":"Bergen Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council"},{"DOI":"10.13039\/501100001824","name":"Czech Science Foundation","doi-asserted-by":"crossref","award":["17-00837S"],"award-info":[{"award-number":["17-00837S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union's Horizon 2020 research and innovation programme ERC Consolidator Grant DISTRUCT","award":["648527"],"award-info":[{"award-number":["648527"]}]},{"name":"Austrian Science Fund","award":["P26696 X-TRACT"],"award-info":[{"award-number":["P26696 X-TRACT"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>We study the first-order (FO) model checking problem of dense graph classes, namely, those that have FO interpretations in (or are FO transductions of) some sparse graph classes. We give a structural characterization of the graph classes that are FO interpretable in graphs of bounded degree. This characterization allows us to efficiently compute such an FO interpretation for an input graph. As a consequence, we obtain an FPT algorithm for successor-invariant FO model checking on any graph class that is FO interpretable in (or an FO transduction of) a graph class of bounded degree. The approach we use to obtain these results may also be of independent interest.<\/jats:p>","DOI":"10.1145\/3383206","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T04:04:52Z","timestamp":1594008292000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["A New Perspective on FO Model Checking of Dense Graph Classes"],"prefix":"10.1145","volume":"21","author":[{"given":"Jakub","family":"Gajarsk\u00fd","sequence":"first","affiliation":[{"name":"Technical University Berlin, Ernst-Reuter-Platz, Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petr","family":"Hlin\u011bn\u00fd","sequence":"additional","affiliation":[{"name":"Masaryk University, Botanick\u00e1, Brno, Czech republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6655-7798","authenticated-orcid":false,"given":"Jan","family":"Obdr\u017e\u00e1lek","sequence":"additional","affiliation":[{"name":"Masaryk University, Botanick\u00e1, Brno, Czech republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"UC Santa Barabara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[{"name":"University of Warwick, Great Britain, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-6(2:2)2010"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the CSL-LICS\u201914","author":"Bova S.","unstructured":"S. Bova , R. Ganian , and S. Szeider . 2014. Model checking existential logic on partially ordered sets . In Proceedings of the CSL-LICS\u201914 . ACM, 1--10. Article No. 21. S. Bova, R. Ganian, and S. Szeider. 2014. Model checking existential logic on partially ordered sets. In Proceedings of the CSL-LICS\u201914. ACM, 1--10. Article No. 21."},{"key":"e_1_2_1_4_1","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Encyclopedia of Mathematics and Its Applications","volume":"138","author":"Courcelle B.","unstructured":"B. Courcelle and J. Engelfriet . 2012 . Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Encyclopedia of Mathematics and Its Applications , Vol. 138 . Cambridge University Press. B. Courcelle and J. Engelfriet. 2012. Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Encyclopedia of Mathematics and Its Applications, Vol. 138. Cambridge University Press."},{"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(99)00184-5"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the LICS\u201907","author":"Dawar A.","unstructured":"A. Dawar , M. Grohe , and S. Kreutzer . 2007. Locally excluding a minor . In Proceedings of the LICS\u201907 . IEEE Computer Society, 270--279. A. Dawar, M. Grohe, and S. Kreutzer. 2007. Locally excluding a minor. In Proceedings of the LICS\u201907. IEEE Computer Society, 270--279."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the ICDT\u201997 (LNCS)","volume":"1186","author":"Dong G.","unstructured":"G. Dong , L. Libkin , and L. Wong . 1997. Local properties of query languages . In Proceedings of the ICDT\u201997 (LNCS) , Vol. 1186 . Springer, 140--154. G. Dong, L. Libkin, and L. Wong. 1997. Local properties of query languages. In Proceedings of the ICDT\u201997 (LNCS), Vol. 1186. Springer, 140--154."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the FOCS\u201910","author":"Dvo\u0159\u00e1k Z.","unstructured":"Z. Dvo\u0159\u00e1k , D. Kr\u00e1\u013e , and R. Thomas . 2010. Deciding first-order properties for sparse graphs . In Proceedings of the FOCS\u201910 . IEEE Computer Society, 133--142. Z. Dvo\u0159\u00e1k, D. Kr\u00e1\u013e, and R. Thomas. 2010. Deciding first-order properties for sparse graphs. In Proceedings of the FOCS\u201910. IEEE Computer Society, 133--142."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the CSL\u201916 (LIPIcs)","volume":"62","author":"Eickmeyer K.","unstructured":"K. Eickmeyer and K. Kawarabayashi . 2016. Successor-invariant first-order logic on graphs with excluded topological subgraphs . In Proceedings of the CSL\u201916 (LIPIcs) , Vol. 62 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 18:1--18:15. K. Eickmeyer and K. Kawarabayashi. 2016. Successor-invariant first-order logic on graphs with excluded topological subgraphs. In Proceedings of the CSL\u201916 (LIPIcs), Vol. 62. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 18:1--18:15."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the LICS\u201912","author":"Engelmann V.","unstructured":"V. Engelmann , S. Kreutzer , and S. Siebertz . 2012. First-order and Monadic second-order model-checking on ordered structures . In Proceedings of the LICS\u201912 . IEEE Computer Society, 275--284. V. Engelmann, S. Kreutzer, and S. Siebertz. 2012. First-order and Monadic second-order model-checking on ordered structures. In Proceedings of the LICS\u201912. IEEE Computer Society, 275--284."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the FOCS\u201915","author":"Gajarsk\u00fd J.","unstructured":"J. Gajarsk\u00fd , P. Hlin\u011bn\u00fd , D. Lokshtanov , J. Obdr\u017e\u00e1lek , S. Ordyniak , M. S. Ramanujan , and S. Saurabh . 2015. FO model checking on posets of bounded width . In Proceedings of the FOCS\u201915 . IEEE Computer Society, 963--974. J. Gajarsk\u00fd, P. Hlin\u011bn\u00fd, D. Lokshtanov, J. Obdr\u017e\u00e1lek, S. Ordyniak, M. S. Ramanujan, and S. Saurabh. 2015. FO model checking on posets of bounded width. In Proceedings of the FOCS\u201915. IEEE Computer Society, 963--974."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the ISAAC\u201914 (LNCS)","volume":"8889","author":"Gajarsk\u00fd J.","unstructured":"J. Gajarsk\u00fd , P. Hlin\u011bn\u00fd , J. Obdr\u017e\u00e1lek , and S. Ordyniak . 2014. Faster existential FO model checking on posets . In Proceedings of the ISAAC\u201914 (LNCS) , Vol. 8889 . Springer, 441--451. J. Gajarsk\u00fd, P. Hlin\u011bn\u00fd, J. Obdr\u017e\u00e1lek, and S. Ordyniak. 2014. Faster existential FO model checking on posets. In Proceedings of the ISAAC\u201914 (LNCS), Vol. 8889. Springer, 441--451."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ICALP\u201918 (LIPIcs)","volume":"107","author":"Gajarsk\u00fd J.","unstructured":"J. Gajarsk\u00fd , S. Kreutzer , J. Ne\u0161et\u0159il , P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toru\u0144czyk. 2018. First-order interpretations of bounded expansion classes . In Proceedings of the ICALP\u201918 (LIPIcs) , Vol. 107 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 126:1--126:14. J. Gajarsk\u00fd, S. Kreutzer, J. Ne\u0161et\u0159il, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toru\u0144czyk. 2018. First-order interpretations of bounded expansion classes. In Proceedings of the ICALP\u201918 (LIPIcs), Vol. 107. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 126:1--126:14."},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"R. Ganian P. Hlin\u011bn\u00fd D. Kr\u00e1\u013e J. Obdr\u017e\u00e1lek J. Schwartz and J. Teska. 2015. FO model checking of interval graphs. Log. Methods Comput. Sci. 11 4:11 (2015) 1--20.  R. Ganian P. Hlin\u011bn\u00fd D. Kr\u00e1\u013e J. Obdr\u017e\u00e1lek J. Schwartz and J. Teska. 2015. FO model checking of interval graphs. Log. Methods Comput. Sci. 11 4:11 (2015) 1--20.","DOI":"10.2168\/LMCS-11(4:11)2015"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the MFCS\u201912 (LNCS)","volume":"7464","author":"Ganian R.","unstructured":"R. Ganian , P. Hlin\u011bn\u00fd , J. Ne\u0161et\u0159il , J. Obdr\u017e\u00e1lek , P. Ossona de Mendez, and R. Ramadurai. 2012. When trees grow low: Shrubs and fast MSO1 . In Proceedings of the MFCS\u201912 (LNCS) , Vol. 7464 . Springer, 419--430. R. Ganian, P. Hlin\u011bn\u00fd, J. Ne\u0161et\u0159il, J. Obdr\u017e\u00e1lek, P. Ossona de Mendez, and R. Ramadurai. 2012. When trees grow low: Shrubs and fast MSO1. In Proceedings of the MFCS\u201912 (LNCS), Vol. 7464. Springer, 419--430."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_2"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the STOC\u201914","author":"Grohe M.","unstructured":"M. Grohe , S. Kreutzer , and S. Siebertz . 2014. Deciding first-order properties of nowhere dense graphs . In Proceedings of the STOC\u201914 . ACM, 89--98. M. Grohe, S. Kreutzer, and S. Siebertz. 2014. Deciding first-order properties of nowhere dense graphs. In Proceedings of the STOC\u201914. ACM, 89--98."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/2586810"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_47"},{"key":"e_1_2_1_23_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer . L. Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00023-9"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1185803625"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"J. van den Heuvel S. Kreutzer M. Pilipczuk D. A. Quiroz R. Rabinovich and S. Siebertz. 2017. Model-checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion. Retrieved from arXiv:1701.08516.  J. van den Heuvel S. Kreutzer M. Pilipczuk D. A. Quiroz R. Rabinovich and S. Siebertz. 2017. Model-checking for Successor-Invariant First-Order Formulas on Graph Classes of Bounded Expansion. Retrieved from arXiv:1701.08516.","DOI":"10.1109\/LICS.2017.8005115"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3383206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3383206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:00Z","timestamp":1750197720000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3383206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,5]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3383206"],"URL":"https:\/\/doi.org\/10.1145\/3383206","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,5]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}