Random-Priority Frontier Routing: Tight Θ(n^c) Bounds Against c-Node Cartels

📄 Download PDF · HTML

This note studies path diversification in trusted-node networks, where sensitive material is relayed through intermediate nodes that may be compromised. It introduces random-priority frontier routing: each vertex gets an independent random priority, and the algorithm repeatedly expands the highest-priority vertex on the global frontier of the explored region. For every fixed cartel size c and every fixed success probability, Θ(n^c) independent executions suffice in the worst case for some route to avoid the cartel. The bound is tight: there are graphs where fewer executions are not enough.

@misc{petrucena2026random,
  title={Random-Priority Frontier Routing: Tight $\Theta(n^c)$ Bounds Against $c$-Node Cartels},
  author={Petru{\v{c}}e{\c{n}}a, Kri{\v{s}}j{\=a}nis},
  year={2026},
  eprint={2609.00893},
  archivePrefix={arXiv},
  primaryClass={cs.DS}
}