SCIENCE@home

Tight bounds for the cover time of multiple random walks

Robert Elsässer,Thomas Sauerwald

Published 2009 in Theoretical Computer Science

ABSTRACT

We study the cover time of multiple random walks. Given a graph G of n vertices, assume that k independent random walks start from the same vertex. The parameter of interest is the speed-up defined as the ratio between the cover time of one and the cover time of k random walks. Recently Alon et al. developed several bounds that are based on the quotient between the cover time and maximum hitting times. Their technique gives a speed-up of *** (k ) on many graphs, however, for many graph classes, k has to be bounded by ${\mathcal{O}}(\log n)$. They also conjectured that, for any 1 ≤ k ≤ n , the speed-up is at most ${\mathcal{O}}(k)$ on any graph. As our main results, we prove the following: We present a new lower bound on the speed-up that depends on the mixing-time. It gives a speed-up of *** (k ) on many graphs, even if k is as large as n . We prove that the speed-up is ${\mathcal{O}}(k \log n)$ on any graph. Under rather mild conditions, we can also improve this bound to ${\mathcal{O}}(k)$, matching exactly the conjecture of Alon et al. We find the correct order of the speed-up for any value of 1 ≤ k ≤ n on hypercubes, random graphs and expanders. For d -dimensional torus graphs (d > 2), our bounds are tight up to a factor of ${\mathcal{O}}(\log n)$. Our findings also reveal a surprisingly sharp dichotomy on several graphs (including d -dim. torus and hypercubes): up to a certain threshold the speed-up is k , while there is no additional speed-up above the threshold.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-39 of 39 references · Page 1 of 1

CITED BY

Showing 1-95 of 95 citing papers · Page 1 of 1