New Distributed Interactive Proofs for Planarity: A Matter of Left and Right

Yuval Gil, Merav Parter · 2025

Read New Distributed Interactive Proofs for Planarity: A Matter of Left and Right by Yuval Gil, Merav Parter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00338.txt.

Introduction

Yuval Gil and Merav Parter give fresh spread proofs for flat graph checks in a 2025 paper on proof tools. In such proofs, a host of nodes checks a claim by short notes from one prover at play. Past work won flat checks in three rounds with lean note size for the claim in hand.

Left and right turns of a walk frame the new route to the same bound in this work. One round with no dice rolls can also hit the bound by tag schemes of like size. Kin graph kinds share the trick, the team notes in the text at hand.

Catalog record

CREATORYuval Gil, Merav Parter
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-00338

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right Thanks: This project is partially funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 949083 Yuval Gil, Merav Parter Abstract We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n n nodes connected by a communication graph G G . The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof size . Prior work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O ⁡ ( log ⁡ n ) O(\log n) . Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O ⁡ ( log ⁡ n ) O(\log n) . In a subsequent work, Bousquet, Feuilloley, and Pierron (OPODIS 2021) achieved the same bound for related graph families such as outerplanarity, series-parallel graphs, and graphs of treewidth at most 2 2 . In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are: • There is a 5 5 -round protocol with O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) proof size for outerplanarity. • There is a 5 5 -round protocol with O ⁡ ( log ⁡ log ⁡ n ) O(\log\log n) proof size for verifying embedded planarity and O ⁡ ( log ⁡ log ⁡ n + log ⁡ Δ ) O(\log\log n+\log\Delta) proof size for general planar graphs, where Δ \Delta is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω ⁡ ( log ⁡ n ) \Omega(\log n) bits for graphs with Δ = O ⁡ ( 1 ) \Delta=O(1) by Feuilloley et al. (PODC 2020). • The non-interactive deterministic lower bound of Ω ⁡ ( log ⁡ n ) \Omega(\log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier’s randomness comes in the form of an unbounded random string shared among the nodes. We also show that our DIPs can be extended to protocols with similar bounds for verifying series-parallel graphs and graphs with tree-width at most 2 2 . Perhaps surprisingly, our results demonstrate that the key technical barrier for obtaining o ⁡ ( log ⁡ log ⁡ n ) o(\log\log n) labels for all our problems is a basic sorting verification task in which all nodes are embedded on an oriented path P ⊆ G P\subseteq G and it is desired for each node to distinguish between its left and right G G -neighbors. 1 Introduction Planarity is a fundamental graph property that has been widely studied due to its rich combinatorial structure and numerous algorithmic applications. While in the centralized setting, the task of verifying if a given graph is planar can be done in linear time [ HT74 ] , in the distributed setting the running time depends linearly on the diameter of the graph [ GH16 ] . The non-local nature of planarity motivates the use of a powerful, but potentially untrusted, prover that can aid the distributed verification by providing each node a short string of advice, a.k.a. a proof label . The nodes then engage in brief communication to collectively determine whether to accept or reject the provided proof. This framework has been formalized into proof labeling schemes by Korman, Kutten and Peleg [ KKP10 ] . In this work we focus on the interactive extension of this model to distributed interactive proofs (DIP) as proposed by Kol, Oshman, and Saxena [ KOS18 ] . In this setting, the nodes are allowed interact with the prover through multiple rounds of communication. The key complexity measures are the number of interaction rounds and the total proof size. The first evidence of the power of such proof systems for certifying planarity was provided by Naor, Parter, and Yogev [ NPY20 ] . Their result for planarity was in fact implied by a more general machinery that translates any (centralized) computation in O(n) time – such as, the centralized planarity verification of [ HT74 ] – into a three-round distributed interactive protocol with O(\log n) proof size. Subsequent work by Feuilloley et al. [ FFM+21 , FFM+23 ] demonstrated that the same proof size could be achieved with just a single interaction round, effectively reducing to the classical proof labeling scheme setting. Their work is accompanied by a matching lower bound of \Omega(\log n) bits, that holds already for graphs with maximum degree of O(1) . These developments bring us back to the fundamental question of whether interaction truly provides an advantage in certifying planarity. Question 1.1 . What is the power of distributed interactive proofs for certifying planarity? We address this question by providing new DIPs for planarity and related graph families. Namely, we obtain constant-round protocols with a proof size of O(\log\log n) for outerplanarity, embedded planarity, series-parallel graphs, and graphs of treewidth at most 2 ; and a proof size of O(\log\log n+\log\Delta) for planarity in graphs of maximum degree \Delta (we distinguish between embedded planarity in which we assume that a graph embedding is given in a distributed manner, and planarity in which no embedding is given; see Section 7 for full details). We also show that the \Omega(\log n) lower bound of [ FFM+21 ] can be extended to one-round DIPs. Therefore, our results give the first evidence to the advantage provided from interaction in planarity certification. Model. In this paper, we consider distributed interactive proofs (DIPs) based on the model of [ KOS18 ] . In the DIP setting, instances are graphs G=(V,E) taken from some universe \mathcal{U} and the goal is to distinguish between yes-instances that come from a yes-family \mathcal{F}_{Y}\subset\mathcal{U} and no-instances that come from a no-family \mathcal{F}_{N}=\mathcal{U}-\mathcal{F}_{Y} . 1 1 1 One can easily adapt the setting so that instances also include some local information to the nodes (e.g., identifiers, weights, etc.). We chose to avoid this additional notation as our results apply to graphs without local node information. A DIP is an interactive protocol between a distributed verifier operating concurrently at all nodes of the graph and a centralized prover that can see the entire instance. The prover and verifier interact back and forth in rounds . Our

Read the complete text