TY - GEN

T1 - Compact Distributed Certification of Planar Graphs

AU - Feuilloley, Laurent

AU - Fraigniaud, Pierre

AU - Montealegre, Pedro

AU - Rapaport, Ivan

AU - Rémila, Éric

AU - Todinca, Ioan

N1 - Publisher Copyright:
© 2020 ACM.

PY - 2020/7/31

Y1 - 2020/7/31

N2 - Naor, Parter, and Yogev (SODA 2020) 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 from 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.

AB - Naor, Parter, and Yogev (SODA 2020) 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 from 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.

KW - communication networks

KW - distributed graph algorithms

KW - fault-tolerance

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

U2 - 10.1145/3382734.3404505

DO - 10.1145/3382734.3404505

M3 - Conference contribution

AN - SCOPUS:85090339501

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 319

EP - 328

BT - PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 39th Symposium on Principles of Distributed Computing, PODC 2020

Y2 - 3 August 2020 through 7 August 2020

ER -