We present a deterministic algorithm that given a tree T with n vertices, a starting vertex v and a slackness parameter epsilon > 0, estimates within an additive error of epsilon the cover and return time, namely, the expected time it takes a simple random walk that starts at v to visit all vertices of T and return to v. The running time of our algorithm is polynomial in n epsilon, and hence remains polynomial in n also for epsilon = 1 n^ O(1) . We also show how the algorithm can be extended to estimate the expected cover (without return) time on trees.
Much of previous work dealt with the cover time from the worst possible starting vertex in the graph. In this case, the maximum hitting time serves as a lower bound on the cover time. Moreover, as shown by Matthews @cite_4 , the cover time can exceed the maximum hitting time by a factor of at most @math . Hence the hitting time (which is computable in deterministic polynomial time) provides a @math approximation to the cover time. An extension of this approach leads to an algorithm with a better approximation ratio of @math @cite_9 . An approach of upper bounding the cover time based on spanning trees is presented in @cite_2 . In particular, when it is applied to trees it implies that the cover and return time is at most @math (which is attained for a path with @math vertices), and for general graphs it gives an upper bound of @math (which can be improved to essentially @math with more careful analysis @cite_7 ). For some graphs, this approach based on spanning trees gives a very good approximation of the cover time.
@cite_9 @cite_4 @cite_7 @cite_2
2136645553 2068008593 2170807097 2048572907
We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M 2<C= O(M(lnlnn) sup 2 ). We give a deterministic-polynomial time algorithm to approximate M within a factor of 2; this then approximates C within a factor of O((lnlnn) sup 2 ), improving the previous bound O(lnn) due to Matthews. The blanket time B was introduced by P. Winkler and D. Zuckerman (1996): it is the expectation of the first time when all vertices are visited within a constant factor of the number of times suggested by the stationary distribution. Obviously C spl les B. Winkler and Zuckerman conjectured B=O(C) and proved B=O(Clnn). Our bounds above are also valid for the blanket time, and so it follows that B=O(C(lnlnn) sup 2 ). On donne des bornes superieures et inferieures sur la fonction generatrice des moments du temps pris par une chaine de Markov pour visiter au moins n des N sous-ensembles selectionnes de son espace d'etats We prove that the expected time for a random walk to cover all n vertices of a graph is at least (1 + o(1))n In n. © 1995 Wiley Periodicals, Inc.