17
$\begingroup$

Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is known to be upper bounded by $O(n^3)$. There are strongly connected digraphs with cover time exponential in $n$. An example of this, is the digraph consisting of a directed cycle $(1, 2, ..., n, 1)$, and edges $(j, 1)$, from vertices $j = 2, ..., n − 1$. Starting from vertex $1$, the expected time for a random walk to reach vertex $n$ is $\Omega(2^n)$. I have two questions :

1) What are the known classes of directed graphs with polynomial cover time ? These classes might be characterized by graph-theoretic properties (or) by properties of the corresponding adjacency matrix (say $A$). For example, if $A$ is symmetric then cover time of the graph is polynomial.

2) Are there more simple examples (like the cycle example mentioned above) where the cover time is exponential ?

3) Are there examples with quasi-polynomial cover time ?

I would appreciate any pointers to good surveys/books on this topic.

$\endgroup$
  • 2
    $\begingroup$ Your cycle example could probably be generalized slightly to graphs with directed girth $g$ with an exponential cover time $2^{\Omega(n/g)}$. $\endgroup$ – Derrick Stolee Nov 12 '10 at 5:55
  • $\begingroup$ Also, expander graphs most likely have fast cover times. $\endgroup$ – Derrick Stolee Nov 12 '10 at 5:57
  • 2
    $\begingroup$ Mihail's paper described how to bound the convergence rates of regular digraphs and even general Markov chains in terms of conductance. It can also be used to bound cover time (I guess). See: ieeexplore.ieee.org/iel2/260/2317/00063529.pdf $\endgroup$ – Zeyu Nov 12 '10 at 6:15
  • 1
    $\begingroup$ @Zeyu, should be an answer ! $\endgroup$ – Suresh Venkat Nov 12 '10 at 6:21
  • 1
    $\begingroup$ A paper of Fan Chung on "Laplacians and the Cheeger Inequality for Directed Graphs" is probably relevant. It also has some pointers to previous work of Fill. springerlink.com/content/pn149711511373w9 $\endgroup$ – Chandra Chekuri Oct 16 '12 at 3:56
7
$\begingroup$

Clearly polynomial mixing time implies polynomial cover time. (Well, not in general. We need the stationary probability at least $1/poly(n)$ at each vertex.) So check Mihail's paper Conductance and convergence of Markov chains-a combinatorial treatment of expanders which proves rapid mixing of regular directed graphs and general Markov chains based on conductance.

Also see the paper Pseudorandom walks on regular digraphs and the RL vs. L problem by Reingold, Trevisan, and Vadhan. Following Mihail's work. They defined the parameter $\lambda_\pi(G)$ which is equivalent to $\lambda_2(G)$, the second largest eigenvalue in absolute value, when the graph $G$ is time-reversible, and remains well-defined for general Markov chains. This parameter is then used to bound the mixing time of $G$.

$\endgroup$
  • $\begingroup$ For mixing times, there is also the related framework work using the so called Poinare constant (which is a generalization of the spectral gap to irreversible setting). Laurent Saloff Coste has some notes (springerlink.com/content/27114435w5149665) treating Markov Chains in this framework. There is also a monograph (faculty.uml.edu/rmontenegro/research/TCS008-journal.pdf) by Tetali and Montenegro. Of course, this is about mixing times, but might be useful for bounding cover time as pointed out by Zeyu. $\endgroup$ – Piyush Oct 19 '11 at 6:05
2
$\begingroup$

Colin Cooper and Alan Frieze have a set of results in the context of random digraphs that might be of interest. They study the properties of a simple random walk on the random directed graph $D_{n,p}$ when $np=d \log n, d>1$. They have proved that:

  • For $d > 1$, whp the cover time of $D_{n,p}$ is asymptotic to $d \log (d/(d-1)) n \log n$. If $d=d(n) \rightarrow \infty$ with $n$, the cover time is asymptotic to $n \log n$.

  • If $p = d \log n/n$ and $d>1$ then whp $C_{G_{n,p}} \sim d \log (d/(d-1)) n \log n$.

  • Let $d>1$ and let $x$ denote the solution in $(0,1)$ of $x = 1-e^{-dx}$. Let $X_g$ be the giant component of $G_{n,p},p=d/n$. Then whp $C_{X_g} \sim \dfrac{dx(2-x)}{4(dx-\log d)} n (\log n)^2$.

  • If $r \geq 3$ is a constant and $G_{n,r}$ denotes a random $r$-regular graph on vertex set $[n]$ with $r \geq 3$ then whp $C_{G_{n,r}} \sim \dfrac{r-1}{r-2} n \log n$.

  • If $m \geq 2$ is a constant and $G_m$ denotes a preferential attachment graph on average degree $2m$ then whp $C_{G_m} \sim \dfrac{2m}{m-1} n \log n$.

  • If $k \geq 3$ and $G_{r,k}$ is a random geometric graph in $\mathcal{R}^k$ of ball size $r$ such that the expected degree of a vertex is asymptotic to $d \log n$, then whp $C_{G_{r,k}} \sim d \log ( \dfrac{d}{d-1}) n \log n$.

See Cooper, C., & Frieze, A. Stationary distribution and cover time of random walks on random digraphs. Journal of Combinatorial Theory, Series B. (2011).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.