{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:53:41Z","timestamp":1781078021736,"version":"3.54.1"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T00:00:00Z","timestamp":1745539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation programme","award":["948057"],"award-info":[{"award-number":["948057"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            Let \u03c6 be a sentence of CMSO\n            <jats:sub>2<\/jats:sub>\n            (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We present a dynamic data structure that for a given graph\n            <jats:italic>G<\/jats:italic>\n            that is updated by edge insertions and edge deletions, maintains whether \u03c6 is satisfied in\n            <jats:italic>G<\/jats:italic>\n            . The data structure is required to correctly report the outcome only when the feedback vertex number of\n            <jats:italic>G<\/jats:italic>\n            does not exceed a fixed constant\n            <jats:italic>k<\/jats:italic>\n            , otherwise it reports that the feedback vertex number is too large. With this assumption, we guarantee amortized update time\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\mathcal {O}}_{\\varphi, k}(\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . If we additionally assume that the feedback vertex number of\n            <jats:italic>G<\/jats:italic>\n            never exceeds\n            <jats:italic>k<\/jats:italic>\n            , this update time guarantee is worst case.\n          <\/jats:p>\n          <jats:p>\n            By combining this result with a classic theorem of Erd\u0151s and P\u00f3sa, we give a fully dynamic data structure that maintains whether a graph contains a packing of\n            <jats:italic>k<\/jats:italic>\n            vertex-disjoint cycles with amortized update time\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\mathcal {O}}_{k}(\\log n)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Our data structure also works in a larger generality of relational structures over binary signatures.\n          <\/jats:p>","DOI":"10.1145\/3715884","type":"journal-article","created":{"date-parts":[[2025,1,29]],"date-time":"2025-01-29T11:44:51Z","timestamp":1738151091000},"page":"1-72","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Maintaining CMSO\n            <sub>2<\/sub>\n            properties on dynamic structures with bounded feedback vertex number"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3922-7953","authenticated-orcid":false,"given":"Konrad","family":"Majewski","sequence":"first","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7891-1988","authenticated-orcid":false,"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"University of Warsaw, Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8309-0141","authenticated-orcid":false,"given":"Marek","family":"Soko\u0142owski","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3395037"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103966"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-57899-4_45"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.50"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009160"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_28"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_27"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0002"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1962.9.1-2.02"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214055"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792226825"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1006\/JAGM.1996.0835"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009227"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1038876"},{"key":"e_1_3_4_19_2","first-page":"181","volume-title":"Model Theoretic Methods in Finite Combinatorics \u2014 AMS-ASL Joint Special Session (Contemporary Mathematics)","author":"Grohe Martin","year":"2009","unstructured":"Martin Grohe and Stephan Kreutzer. 2009. Methods for algorithmic meta theorems. In Model Theoretic Methods in Finite Combinatorics \u2014 AMS-ASL Joint Special Session (Contemporary Mathematics), Martin Grohe and Johann A. Makowsky (Eds.), Vol. 558. American Mathematical Society, 181\u2013206."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2017.68"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08404-6_21"},{"key":"e_1_3_4_23_2","article-title":"FPT-space graph kernelizations","volume":"2007","author":"Kammer Frank","year":"2020","unstructured":"Frank Kammer and Andrej Sajenko. 2020. FPT-space graph kernelizations. CoRR abs\/2007.11643 (2020). arxiv:2007.11643https:\/\/arxiv.org\/abs\/2007.11643","journal-title":"CoRR"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00105"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68535-9_4"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-020-09973-w"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2023.46"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2003.11.002"},{"key":"e_1_3_4_29_2","first-page":"47","article-title":"Parallel tree contraction. part 1: Fundamentals","volume":"5","author":"Miller Gary L.","year":"1989","unstructured":"Gary L. Miller and John H. Reif. 1989. Parallel tree contraction. part 1: Fundamentals. Adv. Comput. Res. 5 (1989), 47\u201372.","journal-title":"Adv. Comput. Res."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.012"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9394-2"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209144"},{"key":"e_1_3_4_33_2","first-page":"173","volume-title":"Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG \u201981), Linz, Austria, June 15\u201317, 1981","author":"Overmars Mark H.","year":"1981","unstructured":"Mark H. Overmars. 1981. Transforming semi-dynamic data structures into dynamic structures. In Proceedings of the 7th Conference Graphtheoretic Concepts in Computer Science (WG \u201981), Linz, Austria, June 15\u201317, 1981, J\u00f6rg R. M\u00fchlbacher (Ed.). Hanser, Munich, Linz, Austria, 173\u2013182."},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFB0014927"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90093-4"},{"key":"e_1_3_4_36_2","first-page":"546","volume-title":"Proceedings of the 36 \\(^{\\textrm {th}}\\)  Annual ACM Symposium on Theory of Computing, STOC 2004","author":"P\u01cetra\u015fcu Mihai","year":"2004","unstructured":"Mihai P\u01cetra\u015fcu and Erik D. Demaine. 2004. Lower bounds for dynamic connectivity. In Proceedings of the 36 \\(^{\\textrm {th}}\\) Annual ACM Symposium on Theory of Computing, STOC 2004. ACM, Chicago, IL, USA, 546\u2013553."},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00308"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90054-P"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715884","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3715884","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:48Z","timestamp":1750295928000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3715884"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,25]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3715884"],"URL":"https:\/\/doi.org\/10.1145\/3715884","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,25]]},"assertion":[{"value":"2023-10-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-12-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-04-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}