# Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Preprint · Fabien Dufoulon, Yuval Emek, Ran Gelles

- Archive id: arxiv:2210.06882
- Published: 2022-10-13
- arXiv: https://arxiv.org/abs/2210.06882
- Citations: 0
- Source URL: https://arxiv.org/abs/2210.06882
- PDF: https://arxiv.org/pdf/2210.06882
- Provenance: arxiv

## Abstract

Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in $O (D \\log\\log n + \\log^3 n)$ rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in $O (D \\log^2 n + \\log^3 n)$ rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the (polynomially-large) hyperedge set of a hypergraph $H = (V\_H, E\_H)$ into $k = Θ(\\log^2 n)$ disjoint subsets $F\_1 \\cup \\cdots \\cup F\_k = E\_H$ such that the (sub-)hypergraph $(V\_H, F\_i)$ is bipartite in the sense that there exists a vertex subset $U \\subseteq V$ such that $\|U \\cap e\| = 1$ for every $e \\in F\_i$. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.