{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:58:55Z","timestamp":1780073935282,"version":"3.54.0"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T00:00:00Z","timestamp":1763942400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T00:00:00Z","timestamp":1763942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We establish that every monadic second-order logic (MSO) formula on graphs with bounded treedepth is decidable in a constant number of rounds within the  model. To our knowledge, this marks the first meta-theorem regarding distributed model checking. Various optimization problems on graphs are expressible in MSO. Examples include determining whether a graph\n                    <jats:italic>G<\/jats:italic>\n                    has a clique of size\n                    <jats:italic>k<\/jats:italic>\n                    , whether it admits a coloring with\n                    <jats:italic>k<\/jats:italic>\n                    \u00a0colors, whether it contains a graph\n                    <jats:italic>H<\/jats:italic>\n                    as a subgraph or minor, or whether terminal vertices in\n                    <jats:italic>G<\/jats:italic>\n                    could be connected via vertex-disjoint paths. Our meta-theorem significantly enhances the work of Bousquet et al. (in: 41st ACM Symposium on Principles of Distributed Computing (PODC), 2022), which was focused on\n                    <jats:italic>distributed certification<\/jats:italic>\n                    of MSO on graphs with bounded treedepth. Moreover, our results can be extended to solving optimization and counting problems expressible in MSO, in graphs of bounded treedepth.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01349-1","type":"journal-article","created":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T11:26:04Z","timestamp":1763983564000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Distributed Model Checking on Graphs of Bounded Treedepth"],"prefix":"10.1007","volume":"88","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,11,24]]},"reference":[{"issue":"5","key":"1349_CR1","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"A Das Sarma","year":"2012","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"1349_CR2","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00446-014-0211-x","volume":"27","author":"P Fraigniaud","year":"2014","unstructured":"Fraigniaud, P., G\u00f6\u00f6s, M., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. Distrib. Comput. 27(6), 419\u2013434 (2014)","journal-title":"Distrib. Comput."},{"key":"1349_CR3","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., G\u00f6\u00f6s, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 157\u2013165 (2013)","DOI":"10.1145\/2484239.2484264"},{"issue":"5","key":"1349_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2499228","volume":"60","author":"P Fraigniaud","year":"2013","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Towards a complexity theory for local distributed computing. J. ACM 60(5), 35\u201313526 (2013)","journal-title":"J. ACM"},{"issue":"1","key":"1349_CR5","first-page":"1","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1\u201333 (2016)","journal-title":"Theory Comput."},{"issue":"4","key":"1349_CR6","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"1349_CR7","first-page":"1","volume":"25","author":"L Blin","year":"2023","unstructured":"Blin, L., Feuilloley, L., Bouder, G.L.: Optimal space lower bound for deterministic self-stabilizing leader election algorithms. Discret. Math. Theor. Comput. Sci. 25, 1\u201317 (2023)","journal-title":"Discret. Math. Theor. Comput. Sci."},{"issue":"3","key":"1349_CR8","first-page":"1","volume":"23","author":"L Feuilloley","year":"2021","unstructured":"Feuilloley, L.: Introduction to local certification. Discret. Math. Theor. Comput. Sci. 23(3), 1\u201323 (2021)","journal-title":"Discret. Math. Theor. Comput. Sci."},{"issue":"4","key":"1349_CR9","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00446-015-0242-y","volume":"28","author":"A Korman","year":"2015","unstructured":"Korman, A., Kutten, S., Masuzawa, T.: Fast and compact self-stabilizing verification, computation, and fault detection of an MST. Distrib. Comput. 28(4), 253\u2013295 (2015)","journal-title":"Distrib. Comput."},{"key":"1349_CR10","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"1349_CR11","doi-asserted-by":"crossref","unstructured":"Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: 33rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 367\u2013376 (2014)","DOI":"10.1145\/2611462.2611493"},{"issue":"7","key":"1349_CR12","doi-asserted-by":"publisher","first-page":"2215","DOI":"10.1007\/s00453-021-00823-w","volume":"83","author":"L Feuilloley","year":"2021","unstructured":"Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., R\u00e9mila, \u00c9., Todinca, I.: Compact distributed certification of planar graphs. Algorithmica 83(7), 2215\u20132244 (2021)","journal-title":"Algorithmica"},{"key":"1349_CR13","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2022.01.023","volume":"909","author":"L Esperet","year":"2022","unstructured":"Esperet, L., L\u00e9v\u00eaque, B.: Local certification of graphs on surfaces. Theor. Comput. Sci. 909, 68\u201375 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"1349_CR14","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/j.dam.2022.10.004","volume":"325","author":"L Feuilloley","year":"2023","unstructured":"Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., R\u00e9mila, \u00c9., Todinca, I.: Local certification of graphs with bounded genus. Discret. Appl. Math. 325, 9\u201336 (2023)","journal-title":"Discret. Appl. Math."},{"key":"1349_CR15","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.tcs.2018.08.020","volume":"811","author":"K Censor-Hillel","year":"2020","unstructured":"Censor-Hillel, K., Paz, A., Perry, M.: Approximate proof-labeling schemes. Theor. Comput. Sci. 811, 112\u2013124 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1349_CR16","doi-asserted-by":"crossref","unstructured":"Feuilloley, L., Bousquet, N., Pierron, T.: What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In: 41st ACM Symposium on Principles of Distributed Computing (PODC), pp. 131\u2013140 (2022)","DOI":"10.1145\/3519270.3538416"},{"key":"1349_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S.: Methods for algorithmic meta theorems. In: Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session, vol. 558, pp. 181\u2013206. AMS, (2009).","DOI":"10.1090\/conm\/558\/11051"},{"issue":"1","key":"1349_CR18","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inf. Comput."},{"key":"1349_CR19","doi-asserted-by":"crossref","unstructured":"Kreutzer, S.: Algorithmic meta-theorems. In: Finite and Algorithmic Model Theory. London Mathematical Society Lecture Note Series, vol. 379, pp. 177\u2013270. Cambridge University Press (2011). http:\/\/www.cs.ox.ac.uk\/people\/stephan.kreutzer\/Publications\/amt-survey.pdf","DOI":"10.1017\/CBO9780511974960.006"},{"key":"1349_CR20","unstructured":"Grohe, M.: Logic, graphs, and algorithms. In: Logic and Automata: History and Perspectives, in Honor of Wolfgang Thomas. Texts in Logic and Games, vol. 2, pp. 357\u2013422. Amsterdam University Press (2008). https:\/\/eccc.weizmann.ac.il\/report\/2007\/091\/"},{"key":"1349_CR21","doi-asserted-by":"crossref","unstructured":"Bousquet, N., Feuilloley, L., Pierron, T.: Local certification of graph decompositions and applications to minor-free classes. In: 25th International Conference on Principles of Distributed Systems (OPODIS). LIPIcs, vol. 217, pp. 22\u201312217. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)","DOI":"10.2139\/ssrn.4223289"},{"issue":"2","key":"1349_CR22","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/S00453-023-01185-1","volume":"86","author":"P Fraigniaud","year":"2024","unstructured":"Fraigniaud, P., Montealegre, P., Rapaport, I., Todinca, I.: A meta-theorem for distributed certification. Algorithmica 86(2), 585\u2013612 (2024). https:\/\/doi.org\/10.1007\/S00453-023-01185-1","journal-title":"Algorithmica"},{"key":"1349_CR23","unstructured":"Fraigniaud, P., Mazoit, F., Montealegre, P., Rapaport, I., Todinca, I.: Distributed certification for classes of dense graphs. In: 37th International Symposium on Distributed Computing (DISC). LIPIcs, vol. 281, pp. 20\u201312017. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"issue":"1","key":"1349_CR24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00446-015-0251-x","volume":"29","author":"J Ne\u0161et\u0159il","year":"2016","unstructured":"Ne\u0161et\u0159il, J., Mendez, P.O.: A distributed low tree-depth decomposition algorithm for bounded expansion classes. Distrib. Comput. 29(1), 39\u201349 (2016)","journal-title":"Distrib. Comput."},{"key":"1349_CR25","doi-asserted-by":"publisher","unstructured":"Ne\u0161et\u0159il, J., Mendez, P.O.: Sparsity - Graphs, Structures, and Algorithms. Algorithms and combinatorics, vol. 28. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"1","key":"1349_CR26","first-page":"1","volume":"11","author":"J Gajarsk\u00fd","year":"2015","unstructured":"Gajarsk\u00fd, J., Hlinen\u00fd, P.: Kernelizing MSO properties of trees of fixed height, and some consequences. Log. Methods Comput. Sci. 11(1), 1\u201326 (2015)","journal-title":"Log. Methods Comput. Sci."},{"issue":"4","key":"1349_CR27","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/2946799","volume":"17","author":"M Elberfeld","year":"2016","unstructured":"Elberfeld, M., Grohe, M., Tantau, T.: Where first-order and monadic second-order logic coincide. ACM Trans. Comput. Log. 17(4), 25 (2016)","journal-title":"ACM Trans. Comput. Log."},{"key":"1349_CR28","doi-asserted-by":"crossref","unstructured":"Garay, J., Kutten, S., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. In: Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science, pp. 659\u2013668. IEEE (1993)","DOI":"10.1109\/SFCS.1993.366821"},{"key":"1349_CR29","doi-asserted-by":"crossref","unstructured":"Censor-Hillel, K., Ghaffari, M., Kuhn, F.: Distributed connectivity decomposition. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 156\u2013165 (2014)","DOI":"10.1145\/2611462.2611491"},{"key":"1349_CR30","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Lenzen, C.: Near-optimal distributed tree embedding. In: International Symposium on Distributed Computing, pp. 197\u2013211. Springer (2014)","DOI":"10.1007\/978-3-662-45174-8_14"},{"key":"1349_CR31","doi-asserted-by":"crossref","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 238\u2013251 (1995)","DOI":"10.1145\/224964.224990"},{"key":"1349_CR32","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Improved distributed steiner forest construction. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pp. 262\u2013271 (2014)","DOI":"10.1145\/2611462.2611464"},{"key":"1349_CR33","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: International Symposium on Distributed Computing, pp. 1\u201315. Springer (2013)","DOI":"10.1007\/978-3-642-41527-2_1"},{"key":"1349_CR34","doi-asserted-by":"crossref","unstructured":"Nanongkai, D., Su, H.-H.: Almost-tight distributed minimum cut algorithms. In: International Symposium on Distributed Computing, pp. 439\u2013453. Springer (2014)","DOI":"10.1007\/978-3-662-45174-8_30"},{"key":"1349_CR35","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Karrenbauer, A., Kuhn, F., Lenzen, C., Patt-Shamir, B.: Near-optimal distributed maximum flow. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pp. 81\u201390 (2015)","DOI":"10.1145\/2767386.2767440"},{"key":"1349_CR36","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing, pp. 489\u2013498 (2016)","DOI":"10.1145\/2897518.2897638"},{"key":"1349_CR37","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"1349_CR38","unstructured":"Ghaffari, M., Parter, M.: Near-optimal distributed dfs in planar graphs. In: 31st International Symposium on Distributed Computing (DISC 2017), pp. 21\u201312116. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)"},{"key":"1349_CR39","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Izumi, T., Zuzic, G.: Low-congestion shortcuts without embedding. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 451\u2013460 (2016)","DOI":"10.1145\/2933057.2933112"},{"key":"1349_CR40","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J.: Efficient distributed decomposition and routing algorithms in minor-free networks and their applications. In: Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, pp. 55\u201366 (2023)","DOI":"10.1145\/3583668.3594604"},{"key":"1349_CR41","unstructured":"Feuilloley, L., Fraigniaud, P.: Survey of distributed decision. Bull. EATCS 119 (2016). https:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/317"},{"key":"1349_CR42","doi-asserted-by":"publisher","first-page":"105643","DOI":"10.1016\/j.jcta.2022.105643","volume":"191","author":"G Elek","year":"2022","unstructured":"Elek, G.: Planarity can be verified by an approximate proof labeling scheme in constant-time. J. Comb. Theory Ser. A 191, 105643 (2022)","journal-title":"J. Comb. Theory Ser. A"},{"key":"1349_CR43","unstructured":"Emek, Y., Gil, Y., Kutten, S.: Locally restricted proof labeling schemes. In: 36th International Symposium on Distributed Computing (DISC). LIPIcs, vol. 246, pp. 20\u201312022. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"key":"1349_CR44","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.jpdc.2022.04.015","volume":"166","author":"L Feuilloley","year":"2022","unstructured":"Feuilloley, L., Fraigniaud, P.: Error-sensitive proof-labeling schemes. J. Parallel Distrib. Comput. 166, 149\u2013165 (2022)","journal-title":"J. Parallel Distrib. Comput."},{"key":"1349_CR45","unstructured":"Esperet, L., Norin, S.: Testability and local certification of monotone properties in minor-closed classes. In: 49th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, vol. 229, pp. 58\u201315815. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"2","key":"1349_CR46","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00446-020-00386-z","volume":"34","author":"L Feuilloley","year":"2021","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A., Perry, M.: Redundancy in distributed proofs. Distrib. Comput. 34(2), 113\u2013132 (2021)","journal-title":"Distrib. Comput."},{"issue":"3","key":"1349_CR47","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s00446-018-0340-8","volume":"32","author":"P Fraigniaud","year":"2019","unstructured":"Fraigniaud, P., Patt-Shamir, B., Perry, M.: Randomized proof-labeling schemes. Distrib. Comput. 32(3), 217\u2013234 (2019)","journal-title":"Distrib. Comput."},{"key":"1349_CR48","unstructured":"Fraigniaud, P., Gall, F.L., Nishimura, H., Paz, A.: Distributed quantum proofs for replicated data. In: 12th Innovations in Theoretical Computer Science Conference (ITCS). LIPIcs, vol. 185, pp. 28\u201312820. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"1349_CR49","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/j.jcss.2018.05.004","volume":"97","author":"A Balliu","year":"2018","unstructured":"Balliu, A., D\u2019Angelo, G., Fraigniaud, P., Olivetti, D.: What can be verified locally? J. Comput. Syst. Sci. 97, 106\u2013120 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"1349_CR50","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.tcs.2020.12.017","volume":"856","author":"L Feuilloley","year":"2021","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J.: A hierarchy of local decision. Theor. Comput. Sci. 856, 51\u201367 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"1349_CR51","unstructured":"Crescenzi, P., Fraigniaud, P., Paz, A.: Trade-offs in distributed interactive proofs. In: 33rd International Symposium on Distributed Computing (DISC). LIPIcs, vol. 146, pp. 13\u201311317. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1349_CR52","doi-asserted-by":"crossref","unstructured":"Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: 37th ACM Symposium on Principles of Distributed Computing (PODC), pp. 255\u2013264. ACM (2018)","DOI":"10.1145\/3212734.3212771"},{"key":"1349_CR53","doi-asserted-by":"crossref","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1096\u2013115. SIAM (2020)","DOI":"10.1137\/1.9781611975994.67"},{"key":"1349_CR54","doi-asserted-by":"crossref","unstructured":"Bick, A., Kol, G., Oshman, R.: Distributed zero-knowledge proofs over networks. In: 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2426\u20132458 (2022)","DOI":"10.1137\/1.9781611977073.97"},{"key":"1349_CR55","unstructured":"Gall, F.L., Miyamoto, M., Nishimura, H.: Distributed quantum interactive proofs. In: 40th International Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol. 254, pp. 42\u201314221. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"issue":"1","key":"1349_CR56","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. III. Planar tree-width. J. Comb. Theory Ser. B 36(1), 49\u201364 (1984). https:\/\/doi.org\/10.1016\/0095-8956(84)90013-3","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5 &6","key":"1349_CR57","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"RB Borie","year":"1992","unstructured":"Borie, R.B., Parker, R.G., Tovey, C.A.: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families. Algorithmica 7(5 &6), 555\u2013581 (1992). https:\/\/doi.org\/10.1007\/BF01758777","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"1349_CR58","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"1349_CR59","unstructured":"Hirvonen, J., Suomela, J.: Distributed Algorithms 2020. Aalto University (2020). https:\/\/jukkasuomela.fi\/da2020\/"},{"key":"1349_CR60","unstructured":"Le\u00a0Gall, F., Miyamoto, M.: Lower bounds for induced cycle detection in distributed computing. In: 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik (2021)"},{"key":"1349_CR61","doi-asserted-by":"publisher","unstructured":"Fischer, O., Gonen, T., Kuhn, F., Oshman, R.: Possibilities and impossibilities for distributed subgraph detection. In: Scheideler, C., Fineman, J.T. (eds.) Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, SPAA 2018, Vienna, Austria, July 16-18, 2018, pp. 153\u2013162. ACM (2018). https:\/\/doi.org\/10.1145\/3210377.3210401","DOI":"10.1145\/3210377.3210401"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01349-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01349-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01349-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T05:12:09Z","timestamp":1770009129000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01349-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,24]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,2]]}},"alternative-id":["1349"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01349-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,24]]},"assertion":[{"value":"31 October 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"10"}}