<p><strike>Clearly polynomial mixing time implies polynomial cover time.</strike> (Well, not in general. We need the stationary probability at least $1/poly(n)$ at each vertex.) So check Mihail's paper <a href="http://ieeexplore.ieee.org/iel2/260/2317/00063529.pdf" rel="nofollow">Conductance and convergence of Markov chains-a combinatorial treatment of expanders</a> which proves rapid mixing of regular directed graphs and general Markov chains based on conductance.</p>

<p>Also see the paper <a href="http://portal.acm.org/citation.cfm?id=1132583" rel="nofollow">Pseudorandom walks on regular digraphs and the RL vs. L problem</a> 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$.</p>

CC BY-SA 3.0
2011-10-19T06:05:51.460Z
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 (http://www.springerlink.com/content/27114435w5149665/) treating Markov Chains in this framework.  There is also a monograph (http://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.
Piyush
CC BY-SA 2.5
2010-11-12T06:55:33.617Z
2010-11-12T18:49:11.513Z
2010-11-12T18:49:11.513Z
Zeyu
<p>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&gt;1$. They have proved that:</p>

<ul>
<li><p>For $d &gt; 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$.</p></li>
<li><p>If $p = d \log n/n$ and $d&gt;1$ then whp $C_{G_{n,p}} \sim d \log (d/(d-1)) n \log n$.</p></li>
<li><p>Let $d&gt;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$.</p></li>
<li><p>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$.</p></li>
<li><p>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$.</p></li>
<li><p>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$.</p></li>
</ul>

<p>See <a href="http://arxiv.org/pdf/1103.4317v1.pdf" rel="nofollow">Cooper, C., &amp; Frieze, A. Stationary distribution and cover time of random walks on random digraphs. Journal of Combinatorial Theory, Series B. (2011).</a></p>

CC BY-SA 3.0
2012-10-10T19:52:03.420Z
2012-10-10T19:52:03.420Z
Juho
<p>Given a random walk on a graph the <strong>cover time</strong> 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 :</p>

<p>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.</p>

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

<p>3) Are there examples with quasi-polynomial cover time ?</p>

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

CC BY-SA 3.0
2012-10-16T03:56:46.180Z
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. http://www.springerlink.com/content/pn149711511373w9/
Chandra Chekuri
CC BY-SA 3.0
2012-10-17T02:48:38.383Z
@ChandraChekuri Thanks for pointing this paper.
Shiva Kintali
CC BY-SA 2.5
2010-11-12T05:55:24.157Z
Your cycle example could probably be generalized slightly to graphs with directed girth $g$ with an exponential cover time $2^{\Omega(n/g)}$.
Derrick Stolee
CC BY-SA 2.5
2010-11-12T05:57:10.850Z
Also, expander graphs most likely have fast cover times.
Derrick Stolee
CC BY-SA 2.5
2010-11-12T06:15:28.440Z
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: http://ieeexplore.ieee.org/iel2/260/2317/00063529.pdf
Zeyu
CC BY-SA 2.5
2010-11-12T06:21:47.443Z
@Zeyu, should be an answer !
Suresh Venkat
<graph-theory><co.combinatorics><markov-chains><random-walks>
Cover Time of Directed Graphs
Shiva Kintali
# Cover Time of Directed Graphs

(Asked by: username_0 on 2010-11-12)

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.

**Tags:** graph-theory, co.combinatorics, markov-chains, random-walks
> **Comments:**
> **username_2**: Your cycle example could probably be generalized slightly to graphs with directed girth $g$ with an exponential cover time $2^{\Omega(n/g)}$.  
> **username_2**: Also, expander graphs most likely have fast cover times.  
> **username_3**: 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: http://ieeexplore.ieee.org/iel2/260/2317/00063529.pdf  
> **username_4**: @Zeyu, should be an answer !  
> **username_1**: 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. http://www.springerlink.com/content/pn149711511373w9/  
> **username_0**: @ChandraChekuri Thanks for pointing this paper.  

---

## 2 answers

### Answer by username_3 on 2010-11-12. Score: 7

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](http://ieeexplore.ieee.org/iel2/260/2317/00063529.pdf) 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](http://portal.acm.org/citation.cfm?id=1132583) 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$.

> **Comments:**
> **username_5**: 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 (http://www.springerlink.com/content/27114435w5149665/) treating Markov Chains in this framework.  There is also a monograph (http://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.  

---

### Answer by username_6 on 2012-10-10. Score: 2

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).](http://arxiv.org/pdf/1103.4317v1.pdf)


---

