Tight bounds for the cover time of multiple random walks (Q541669)

The authors study the cover time of \(k\) parallel, independent random walks on undirected graphs that start from the same vertex. The speed-up is defined as the ratio of the cover time of a single random walk to the cover time of these \(k\) random walks. The authors present a new lower bound on the speed-up that depends on the mixing time. It gives a speed-up of \(\Omega(k)\) on many graphs, even if \(k\) is as large as \(n\). They also prove that the speed-up is \(O(k \log n)\) on any graph. For a large class of graphs they improve this bound to \(O(k)\), matching a conjecture of \textit{N. Alon} et al. [``Many random walks are faster than one'', in: 20th annual ACM symposium on parallel algorithms and architectures (SPAA 2008), 119--128 (2008)]. They determine the order of the speed-up for any value of \(1\leq k\leq n\) on hypercubes, random graphs and degree restricted expanders. Their findings reveal a surprisingly sharp threshold behaviour for certain graphs, e.g., the \(d\)-dimensional torus with \(d>2\) and hypercubes.