Bounds on the cover time of parallel rotor walks

• DOI: 10.1016/j.jcss.2016.01.004
• Publication Date: 2016-03-09T17:17:12Z
• Authors: Dariusz Dereniowski; Adrian Kosowski; Dominik Pająk; Przemysław Uznański
• Keywords: Initialization; Undirected graph

We consider the cover time of multi-agent rotor-router.Rotor-router is a deterministic process in which the environment determines moves of the agents.Rotor-router is a form of derandomization of the random walk.We show that k agents explore any graph between ? ( log ? k ) and ? ( k ) faster than single agent.It is conjectured that the speedup for multiple random walks is also between ? ( log ? k ) and ? ( k ) . The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the initialization of the walks. We show that for any graph with m edges and diameter D, this cover time is at most ? ( m D / log ? k ) and at least ? ( m D / k ) , which corresponds to a speedup of between ? ( log ? k ) and ? ( k ) with respect to the cover time of a single walk.