{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:40:07Z","timestamp":1767314407627,"version":"3.48.0"},"publisher-location":"Cham","reference-count":14,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032118349","type":"print"},{"value":"9783032118356","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-11835-6_14","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:36:59Z","timestamp":1767314219000},"page":"192-204","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Reductions in\u00a0Local Certification"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6200-0514","authenticated-orcid":false,"given":"Louis","family":"Esperet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2675-8581","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Zeitoun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"14_CR1","doi-asserted-by":"publisher","unstructured":"Defrain, O., Esperet, L., Lagoutte, A., Morin, P., Raymond, J.: Local certification of geometric graph classes. In: Kr\u00e1lovic, R., Kucera, A. (eds.) 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, 26\u201330 August 2024, Bratislava, Slovakia. LIPIcs, vol.\u00a0306, pp. 48:1\u201348:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2024.48","DOI":"10.4230\/LIPICS.MFCS.2024.48"},{"key":"14_CR2","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. Theoret. Comput. Sci. 909, 68\u201375 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.01.023","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR3","unstructured":"Esperet, L., Zeitoun, S.: Reductions in local certification (2025). https:\/\/arxiv.org\/abs\/2502.01551"},{"key":"14_CR4","doi-asserted-by":"publisher","unstructured":"Feuilloley, L.: Introduction to local certification. Discret. Math. Theor. Comput. Sci. 23(3) (2021). https:\/\/doi.org\/10.46298\/DMTCS.6280","DOI":"10.46298\/DMTCS.6280"},{"key":"14_CR5","doi-asserted-by":"publisher","unstructured":"Feuilloley, L., Bousquet, N., Pierron, T.: What can be certified compactly? Compact local certification of MSO properties in tree-like graphs. In: Milani, A., Woelfel, P. (eds.) PODC 2022: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, 25\u201329 July 2022, pp. 131\u2013140. ACM (2022). https:\/\/doi.org\/10.1145\/3519270.3538416","DOI":"10.1145\/3519270.3538416"},{"issue":"7","key":"14_CR6","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). https:\/\/doi.org\/10.1007\/s00453-021-00823-w","journal-title":"Algorithmica"},{"key":"14_CR7","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). https:\/\/doi.org\/10.1016\/j.dam.2022.10.004","journal-title":"Discret. Appl. Math."},{"key":"14_CR8","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Mazoit, F., Montealegre, P., Rapaport, I., Todinca, I.: Distributed certification for classes of dense graphs. In: Oshman, R. (ed.) 37th International Symposium on Distributed Computing, DISC 2023, 10\u201312 October 2023, L\u2019Aquila, Italy. LIPIcs, vol.\u00a0281, pp. 20:1\u201320:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPICS.DISC.2023.20","DOI":"10.4230\/LIPICS.DISC.2023.20"},{"key":"14_CR9","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Montealegre, P., Rapaport, I., Todinca, I.: A meta-theorem for distributed certification. In: Parter, M. (ed.) SIROCCO 2022. LNCS, vol. 13298, pp. 116\u2013134. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-09993-9_7","DOI":"10.1007\/978-3-031-09993-9_7"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). https:\/\/doi.org\/10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"14_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a019","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). https:\/\/doi.org\/10.4086\/toc.2016.v012a019","journal-title":"Theory Comput."},{"key":"14_CR12","doi-asserted-by":"publisher","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 January 2020, pp. 1096\u2013115. SIAM (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.67","DOI":"10.1137\/1.9781611975994.67"},{"issue":"1\u20133","key":"14_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/0012-365X(94)90277-1","volume":"126","author":"IA Stewart","year":"1994","unstructured":"Stewart, I.A.: Deciding whether a planar graph has a cubic subgraph is NP-complete. Discret. Math. 126(1\u20133), 349\u2013357 (1994). https:\/\/doi.org\/10.1016\/0012-365X(94)90277-1","journal-title":"Discret. Math."},{"issue":"1\u20133","key":"14_CR14","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/0012-365X(95)00324-P","volume":"163","author":"IA Stewart","year":"1997","unstructured":"Stewart, I.A.: On locating cubic subgraphs in bounded-degree connected bipartite graphs. Discret. Math. 163(1\u20133), 319\u2013324 (1997). https:\/\/doi.org\/10.1016\/0012-365X(95)00324-P","journal-title":"Discret. Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-11835-6_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T00:37:00Z","timestamp":1767314220000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-11835-6_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032118349","9783032118356"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-11835-6_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Otzenhausen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo.uni-trier.de\/wg2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}