A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs
Distributed networks are prone to errors so verifying their output is critical. We develop local certification protocols for graph properties in which nodes are given certificates that allow them to check whether the network as a whole satisfies some fixed property while only communicating with their local network. Instead of considering a specific problem and developing a local certification protocol tailor-made for the problem, we aim for generic protocols that can certify any property expressible in a certain logical framework.
Authors
- Tomáš Masařík (ORCID: https://orcid.org/0000-0001-8524-4036)
- L. F. Cook (ORCID: https://orcid.org/0000-0002-1516-5874)
- Eun Jung Kim (ORCID: https://orcid.org/0000-0002-6824-0516)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Korea Advanced Institute of Science and Technology (KR)
- Institute for Basic Science (KR)
- University of Warsaw (PL)
- University of Amsterdam (NL)
Publication Details
- Published
- 2025-06-13
- DOI
- https://doi.org/10.1145/3732772.3733562
- Citations
- 1
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 1.50
Funders
- European Commission
- National Research Foundation
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek
- Institute for Basic Science