Compact Distributed Certification of Planar Graphs

Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

16 Citas (Scopus)

Resumen

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–115, 2020. https://doi.org/10.1137/1.9781611975994.67) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in n-node networks. We show that a single interaction with the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no proof-labeling schemes—in fact, even no locally checkable proofs—for planarity using certificates on o(log n) bits.

Idioma originalInglés
Páginas (desde-hasta)2215-2244
Número de páginas30
PublicaciónAlgorithmica
Volumen83
N.º7
DOI
EstadoPublicada - jul. 2021

Huella

Profundice en los temas de investigación de 'Compact Distributed Certification of Planar Graphs'. En conjunto forman una huella única.

Citar esto