Compact Distributed Certification of Planar Graphs

Autor:	Feuilloley, Laurent, Fraigniaud, Pierre, Rapaport, Ivan, Rémila, Éric, Montealegre, Pedro, Todinca, Ioan
Rok vydání:	2020
Předmět:	Computer Science - Distributed Parallel and Cluster Computing Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{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 \emph{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 \emph{locally checkable proofs} -- for planarity using certificates on $o(\log n)$ bits. Comment: To appear at PODC 2020
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2005.05863 Zobrazit plný text záznamu View this record from Arxiv