2025/10/21 by Gil, Yuval, Parter, Merav
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2510.18592
We provide new communication-efficient distributed interactive proofs for planarity. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the prover is a single centralized entity whose goal is to prove a certain claim regarding an input graph G. To do so, the prover communicates with a distributed verifier that operates concurrently on all n nodes of G. A DIP is measured by the amount of prover-verifier communication it requires. Namely, the goal is to design a DIP with a small number of interaction rounds and a small proof size, i.e., a small amount of communication per round. Our main result is an O(log *n)-round DIP protocol for embedded planarity and planarity with a proof size of O(1) and O(\lceillog Δ/log *n\rceil), respectively. In fact, this result can be generalized as follows. For any 1≤ r≤ log*n, there exists an O(r)-round protocol for embedded planarity and planarity with a proof size of O(log (r)n) and O(log (r)n+log Δ/r), respectively.