TY - JOUR

T1 - Local certification of graphs with bounded genus

AU - Feuilloley, Laurent

AU - Fraigniaud, Pierre

AU - Montealegre, Pedro

AU - Rapaport, Ivan

AU - Rémila, Éric

AU - Todinca, Ioan

N1 - Funding Information:
Additional funding from Institute for Research in Market Imperfections and Public Policy (MIPP) and ANR project GrR (ANR-18-CE40-0032).Additional funding from ANR project DESCARTES, and INRIA project GANG.Additional funding from ANID via PAI + Convocatoria Nacional Subvención a la Incorporación en la Academia Año 2017 + PAI77170068 and FONDECYT11190482.Additional funding from CONICYT via PIA/Apoyo a Centros Científicos y Tecnológicos de ExcelenciaAFB 170001 and Fondecyt1220142.Additional funding from IDEX LYON (project INDEPTH) within ANR-16-IDEX-0005 and MODMAD.
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2023/1/30

Y1 - 2023/1/30

N2 - Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(logn)) protocol for this class, that is, a distributed interactive protocol with O(logn)-bit proof size in n-node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a dMAM(O(logn)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(logn) bits. This result also holds for the class of graphs with bounded non-orientable genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus.

AB - Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(logn)) protocol for this class, that is, a distributed interactive protocol with O(logn)-bit proof size in n-node graphs, and three interactions between the (centralized) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a dMAM(O(logn)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(logn) bits. This result also holds for the class of graphs with bounded non-orientable genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded non-orientable genus.

KW - Distributed graph algorithms

KW - Local certification

KW - Locally checkable proofs

KW - Proof-labeling scheme

UR - http://www.scopus.com/inward/record.url?scp=85140920312&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2022.10.004

DO - 10.1016/j.dam.2022.10.004

M3 - Article

AN - SCOPUS:85140920312

SN - 0166-218X

VL - 325

SP - 9

EP - 36

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -