← 研踪 PaperTrailarXiv:2511.19208 · v4
Leader Election via Unique Sink Orientation
首次提交 2025-11-24 23:17
版本更新 2026-11-09 23:23
雷达观测 2026-11-10 15:22
摘要
A proof-labeling scheme (PLS) certifies a global property using only local checks. That is, a prover assigns a certificate to every node and each node accepts or rejects by inspecting only the certificates in its neighborhood, so that every graph satisfying some global property admits a certificate assignment accepted by all nodes (existence) and every certificate assignment accepted by all nodes gives a legal configuration (soundness). In this work, we design PLSs for two classical problems, leader certification and spanning tree certification, assuming that all nodes are anonymous, for a specific class of graphs. Certifying a unique leader is impossible in general anonymous graphs for any certificate size due to a well-known result for rings by [Korman, Kutten and Peleg, 2010]. This raises the question of which graph classes admit a PLS for leader certification with anonymous nodes, ideally with size independent of the size of the graph. Our work contributes to a growing list of such classes, which includes chordal graphs, meshed graphs and simply connected subsets of the triangular grid. We consider dismantlable graphs, a class which contains trees, chordal, bridged and Helly graphs, as well as the $k$-th powers of $δ$-hyperbolic graphs for $k \geq 2δ$. To the best of our knowledge, these are the first PLSs tailored to dismantlable graphs, potentially highlighting structural properties useful for certifying additional problems. Finally, we present a generic transformation that converts any labeling scheme with certificates of finite type into a silent self-stabilizing algorithm by adding only one extra state, assuming a Gouda fair scheduler, whereas known generic transformations require $O(\ell + \log n)$ bits for $\ell$-bit certificates. This transformation may be of independent interest.
作者备注：18 pages, 4 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v4 · 2026-11-09 23:23 · 最新观测版本
Leader Election via Unique Sink Orientation
A proof-labeling scheme (PLS) certifies a global property using only local checks. That is, a prover assigns a certificate to every node and each node accepts or rejects by inspecting only the certificates in its neighborhood, so that every graph satisfying some global property admits a certificate assignment accepted by all nodes (existence) and every certificate assignment accepted by all nodes gives a legal configuration (soundness). In this work, we design PLSs for two classical problems, leader certification and spanning tree certification, assuming that all nodes are anonymous, for a specific class of graphs. Certifying a unique leader is impossible in general anonymous graphs for any certificate size due to a well-known result for rings by [Korman, Kutten and Peleg, 2010]. This raises the question of which graph classes admit a PLS for leader certification with anonymous nodes, ideally with size independent of the size of the graph. Our work contributes to a growing list of such classes, which includes chordal graphs, meshed graphs and simply connected subsets of the triangular grid. We consider dismantlable graphs, a class which contains trees, chordal, bridged and Helly graphs, as well as the $k$-th powers of $δ$-hyperbolic graphs for $k \geq 2δ$. To the best of our knowledge, these are the first PLSs tailored to dismantlable graphs, potentially highlighting structural properties useful for certifying additional problems. Finally, we present a generic transformation that converts any labeling scheme with certificates of finite type into a silent self-stabilizing algorithm by adding only one extra state, assuming a Gouda fair scheduler, whereas known generic transformations require $O(\ell + \log n)$ bits for $\ell$-bit certificates. This transformation may be of independent interest.
查看此版本解读 →查看此版本原文 ↗