← 研踪 PaperTrailarXiv:2611.23540 · v1
Size-Independent Survival Bounds for Routing Without a Map
首次提交 2026-11-18 05:47
版本更新 2026-11-18 05:47
雷达观测 2026-11-19 19:08
摘要
A walker, such as a packet carrying a secret share, must reach a known target in an unknown graph while avoiding a fixed set of fatal vertices (compromised relays in the packet interpretation). It learns a vertex's neighbours only on reaching that vertex safely, remembers its observations, and is promised a safe route. We prove that a randomised depth-first strategy guarantees a success probability depending only on the maximum degree and the number of fatal vertices, not on the size of the graph. Planarity is not required for this guarantee, and planar examples attain the bound at every sufficiently large graph size. At those sizes, when the degree cap is at least three, the guarantee is optimal among strict depth-first strategies. Whether strategies allowed to switch between unfinished branches can guarantee a larger worst-case survival probability remains open. For unknown trees and for graphs of maximum degree two, we determine the exact best worst-case success probability over all routing strategies. Explicit examples compare our strategy with random-priority frontier routing and ordinary random walks, showing how exploration order can prevent survival probability from declining as the graph grows.
作者备注:38 pages, 11 figures. Follow-up to arXiv:2609.00893
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 05:47 · 最新观测版本
Size-Independent Survival Bounds for Routing Without a Map
A walker, such as a packet carrying a secret share, must reach a known target in an unknown graph while avoiding a fixed set of fatal vertices (compromised relays in the packet interpretation). It learns a vertex's neighbours only on reaching that vertex safely, remembers its observations, and is promised a safe route. We prove that a randomised depth-first strategy guarantees a success probability depending only on the maximum degree and the number of fatal vertices, not on the size of the graph. Planarity is not required for this guarantee, and planar examples attain the bound at every sufficiently large graph size. At those sizes, when the degree cap is at least three, the guarantee is optimal among strict depth-first strategies. Whether strategies allowed to switch between unfinished branches can guarantee a larger worst-case survival probability remains open. For unknown trees and for graphs of maximum degree two, we determine the exact best worst-case success probability over all routing strategies. Explicit examples compare our strategy with random-priority frontier routing and ordinary random walks, showing how exploration order can prevent survival probability from declining as the graph grows.
查看此版本解读 →查看此版本原文 ↗