{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T22:35:17Z","timestamp":1784673317146,"version":"3.55.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR project TWIN-WIDTH","award":["ANR-21-CE48-0014-01"],"award-info":[{"award-number":["ANR-21-CE48-0014-01"]}]},{"name":"ANR project DIGRAPHS","award":["ANR-19-CE48-0013-01"],"award-info":[{"award-number":["ANR-19-CE48-0013-01"]}]},{"name":"ANR project ASSK","award":["ANR-18-CE40-0025-01"],"award-info":[{"award-number":["ANR-18-CE40-0025-01"]}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,2,28]]},"abstract":"<jats:p>\n            Inspired by a\n            <jats:italic>width<\/jats:italic>\n            invariant defined on permutations by Guillemot and Marx [SODA\u201914], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs,\n            <jats:italic>\n              K\n              <jats:sub>t<\/jats:sub>\n            <\/jats:italic>\n            -free unit\n            <jats:italic>d<\/jats:italic>\n            -dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a\n            <jats:italic>\n              sequence of\n              <jats:italic>d<\/jats:italic>\n              -contractions\n            <\/jats:italic>\n            , witness that the twin-width is at most\n            <jats:italic>d<\/jats:italic>\n            . We show that FO model checking, that is deciding if a given first-order formula \u03d5 evaluates to true for a given binary structure\n            <jats:italic>G<\/jats:italic>\n            on a domain\n            <jats:italic>D<\/jats:italic>\n            , is FPT in |\u03d5| on classes of bounded twin-width, provided the witness is given. More precisely, being given a\n            <jats:italic>d<\/jats:italic>\n            -contraction sequence for\n            <jats:italic>G<\/jats:italic>\n            , our algorithm runs in time\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            ,|\u03d5 |) \u00b7 |D| where\n            <jats:italic>f<\/jats:italic>\n            is a computable but non-elementary function. We also prove that bounded twin-width is preserved under FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarsk\u00fd et al. [FOCS\u201915].\n          <\/jats:p>","DOI":"10.1145\/3486655","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T01:58:53Z","timestamp":1638237533000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":63,"title":["Twin-width I: Tractable FO Model Checking"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1653-5822","authenticated-orcid":false,"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[{"name":"Univ Lyon, CNRS, ENS de Lyon, Universit\u00e9 Claude-Bernard Lyon 1, LIP UMR5668, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Dauphine, PSL University, CNRS UMR, LAMSADE France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"St\u00e9phan","family":"Thomass\u00e9","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lyon (COMUE), CNRS, ENS de Lyon, Universit\u00e9 Claude-Bernard Lyon 1, LIP France and Institut Universitaire de France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R\u00e9mi","family":"Watrigant","sequence":"additional","affiliation":[{"name":"Univ Lyon, CNRS, ENS de Lyon, Universit\u00e9 Claude-Bernard Lyon 1, LIP UMR5668, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"key":"e_1_3_2_2_2","article-title":"Twin-width is linear in the poset width","volume":"2106","author":"Balab\u00e1n Jakub","year":"2021","unstructured":"Jakub Balab\u00e1n and Petr Hlinen\u00fd. 2021. Twin-width is linear in the poset width. CoRR abs\/2106.15337 (2021). arXiv:2106.15337 https:\/\/arxiv.org\/abs\/2106.15337.","journal-title":"CoRR"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.011"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-6(2:2)2010"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3458064.3458182"},{"key":"e_1_3_2_7_2","first-page":"35:1\u201335:20","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs)","volume":"198","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet, Colin Geniet, Eun Jung Kim, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2021. Twin-width III: Max independent set, min dominating set, and coloring. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.), Vol. 198. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 35:1\u201335:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.35"},{"key":"e_1_3_2_8_2","article-title":"Twin-width VII: Groups and the small conjecture","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet, Colin Geniet, Romain Tessera, and St\u00e9phan Thomass\u00e9. 2021. Twin-width VII: Groups and the small conjecture. In Preparation (2021).","journal-title":"In Preparation"},{"key":"e_1_3_2_9_2","article-title":"Twin-width IV: Ordered graphs and matrices","volume":"2102","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, St\u00e9phan Thomass\u00e9, and Szymon Toru\u0144czyk. 2021. Twin-width IV: Ordered graphs and matrices. CoRR abs\/2102.03117 (2021). arXiv:2102.03117 https:\/\/arxiv.org\/abs\/2102.03117.","journal-title":"CoRR"},{"key":"e_1_3_2_10_2","article-title":"Twin-width VI: The lens of contraction sequences","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet, Eun Jung Kim, Amadeus Reinald, and St\u00e9phan Thomass\u00e9. 2021. Twin-width VI: The lens of contraction sequences. Manuscript (2021).","journal-title":"Manuscript"},{"key":"e_1_3_2_11_2","article-title":"Twin-width and polynomial kernels","volume":"2107","author":"Bonnet \u00c9douard","year":"2021","unstructured":"\u00c9douard Bonnet, Eun Jung Kim, Amadeus Reinald, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2021. Twin-width and polynomial kernels. CoRR abs\/2107.02882 (2021). arXiv:2107.02882 https:\/\/arxiv.org\/abs\/2107.02882.","journal-title":"CoRR"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814937"},{"key":"e_1_3_2_13_2","article-title":"F\u00fcredi-hajnal limits are typically subexponential","volume":"1607","author":"Cibulka Josef","year":"2016","unstructured":"Josef Cibulka and Jan Kyncl. 2016. F\u00fcredi-hajnal limits are typically subexponential. CoRR abs\/1607.07491 (2016). arXiv:1607.07491 http:\/\/arxiv.org\/abs\/1607.07491.","journal-title":"CoRR"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55751-8_17"},{"issue":"2","key":"e_1_3_2_18_2","article-title":"The first order properties of products of algebraic systems","volume":"32","author":"Feferman Solomon","year":"1967","unstructured":"Solomon Feferman and Robert L. Vaught. 1967. The first order properties of products of algebraic systems. Journal of Symbolic Logic 32, 2 (1967).","journal-title":"Journal of Symbolic Logic"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_3_2_20_2","article-title":"Stanley-Wilf limits are typically exponential","volume":"1310","author":"Fox Jacob","year":"2013","unstructured":"Jacob Fox. 2013. Stanley-Wilf limits are typically exponential. CoRR abs\/1310.8378 (2013). arXiv:1310.8378 http:\/\/arxiv.org\/abs\/1310.8378.","journal-title":"CoRR"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"e_1_3_2_23_2","first-page":"105","volume-title":"Studies in Logic and the Foundations of Mathematics","author":"Gaifman Haim","year":"1982","unstructured":"Haim Gaifman. 1982. On local and non-local properties. In Studies in Logic and the Foundations of Mathematics. Vol. 107. Elsevier, 105\u2013135."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.63"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3383206"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(4:8)2015"},{"key":"e_1_3_2_27_2","first-page":"56:1\u201356:17","volume-title":"37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10\u201313, 2020, Montpellier, France (LIPIcs)","author":"Gajarsk\u00fd Jakub","year":"2020","unstructured":"Jakub Gajarsk\u00fd and Stephan Kreutzer. 2020. Computing shrub-depth decompositions. In 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10\u201313, 2020, Montpellier, France (LIPIcs), Christophe Paul and Markus Bl\u00e4ser (Eds.), Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 56:1\u201356:17. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.56"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382093"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-11(4:11)2015"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634081"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2018.10.001"},{"key":"e_1_3_2_33_2","first-page":"131","article-title":"Parameterized complexity of first-order logic","volume":"16","author":"Kreutzer Stephan","year":"2009","unstructured":"Stephan Kreutzer and Anuj Dawar. 2009. Parameterized complexity of first-order logic. Electronic Colloquium on Computational Complexity (ECCC) 16 (2009), 131. http:\/\/eccc.hpi-web.de\/report\/2009\/131.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3118216.3118283"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.04.002"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/2675656"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11050"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_2_40_2","unstructured":"Martin Vatshelle. 2012. New width parameters of graphs. (2012)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486655","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3486655","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:46Z","timestamp":1750191526000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486655"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,29]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,28]]}},"alternative-id":["10.1145\/3486655"],"URL":"https:\/\/doi.org\/10.1145\/3486655","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,29]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}