The Power of Two Choices for Random Walks

DOI10.1017/S0963548321000183MaRDI QIDQ6329058arXivFDO

Authors Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, John Sylvester

Publication date 12 November 2019

Published in arXiv

Full work available at URL https://doi.org/10.1017/S0963548321000183

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.DMmath.COmath.PR

Abstract: We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the controller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number $n$ of vertices on discrete tori and bounded degree trees, of order $mathcalO(nloglogn)$ on bounded degree expanders, and of order $mathcalO(n(loglogn{)}^2)$ on the ErdH{o}s-R'{e}nyi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy, and prove a dichotomy in efficiency between computing strategies for hitting and cover times.

This page was built for publication: The Power of Two Choices for Random Walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6329058)