Near-optimal dispersion on arbitrary anonymous graphs

Abstract

Given an undirected, anonymous, port-labeled graph of n memory-less nodes, m edges, and degree Δ, we consider the problem of dispersing k ≤ n robots (or tokens) positioned initially arbitrarily on the nodes of the graph to exactly k different nodes, one on each node. The objective is to simultaneously minimize time and memory requirement at each robot. The best previously known algorithm solves this problem in O ( min ⁡ { m , k Δ } ⋅ log ⁡ ℓ ) time storing O ( log ⁡ ( k + Δ ) ) bits at each robot, where ℓ ≤ k / 2 is the number of nodes with multiple robots positioned on them in the initial configuration. In this paper, we present a novel multi-source DFS traversal algorithm solving this problem in O ( min ⁡ { m , k Δ } ) time with O ( log ⁡ ( k + Δ ) ) bits at each robot. The memory complexity of our algorithm is already asymptotically optimal and the time complexity is asymptotically optimal for the graphs of constant degree Δ = O ( 1 ) . The result holds in both synchronous and asynchronous settings.