The evolution of the cover time
From MaRDI portal
Abstract: The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovasz and Vu yielded a (log log n)^2 polynomial time approximation. We refine this upper bound, and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdos-Renyi random graph G(n,c/n) in the supercritical regime with c>1 fixed, is asymptotic to f(c) n log^2 n, where f(c) tends to 1 as c tends to 1. However, our new bound implies that the cover time for the critical Erdos-Renyi random graph G(n,1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0,1}^n, on high-girth expanders, and on tori Z_n^d for fixed large d. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman, is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.
Recommendations
Cites work
- A tight lower bound on the cover time for random walks on graphs
- A tight upper bound on the cover time for random walks on graphs
- An introduction to covering problems for random walks on graphs
- Building uniformly random subtrees
- Component behavior near the critical point of the random graph process
- Continuity of local times for L�vy processes
- Covering problems for Markov chains
- Critical random graphs: Diameter and mixing time
- Diameters in supercritical random graphs via first passage percolation
- Edge percolation on a random regular graph of low degree
- scientific article; zbMATH DE number 1436000 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- Mean-field conditions for percolation on finite graphs
- Multiple cover time
- Random graph asymptotics on high-dimensional tori
- Random subgraphs of finite graphs: I. The scaling window under the triangle condition
- Random walk covering of some special trees
- Random walks and the effective resistance of networks
- The Alexander-Orbach conjecture holds in high dimensions
- The cover time of the giant component of a random graph
- The electrical resistance of a graph captures its commute and cover times
- The Generic Chaining
- The sizes of compact subsets of Hilbert space and continuity of Gaussian processes
- Universal traversal sequences for paths and cycles
Cited in
(17)- An upper bound on the cover time for powers of graphs
- A spectral characterization for concentration of the cover time
- Cover times for sequences of reversible Markov chains on random graphs
- Improved approximation of the minimum cover time
- The cover time of sparse random graphs
- The cover time of the giant component of a random graph
- Sandwich theorem of cover times
- Cover times, blanket times, and majorizing measures
- scientific article; zbMATH DE number 716161 (Why is no real title available?)
- Deterministic approximation of the cover time
- Analytical results for the distribution of cover times of random walks on random regular graphs
- On the cover time of the emerging giant
- Cover time of a random graph with a degree sequence. II: Allowing vertices of degree two.
- Cover time and broadcast time
- Cover times and generic chaining
- Cover times, blanket times, and majorizing measures
- Convergence of blanket times for sequences of random walks on critical random graphs
This page was built for publication: The evolution of the cover time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2998848)
