# Examples for directed graphs with super polynomial cover time

The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes.

For undirected graphs the cover time is upperbounded by $O(n^3)$. What about directed graphs? I'm looking for examples of super-polynomial cover time.

Is there an example for such graph with $O(2^{\sqrt n})$ cover time?

Yes, it's not too hard to construct such a graph. Consider a path $v_1 \to v_2 \to v_3 \to \dots \to v_n$ containing $n$ vertices. Now add a new "dead-end vertex" $w$, and add edges $v_1 \to w$, $v_2 \to w$, $v_3 \to w$, etc.
If you do a random walk starting at $v_1$, the probability that you reach $v_n$ is $1/2^{n-1}$, as you have to get lucky and move in the right direction at each of the vertices $v_1,\dots,v_{n-1}$ to avoid getting stuck at the dead end. Therefore, the cover time will be $\Omega(2^n)$.
Notice how things would change if we converted this into an undirected graph. In an undirected graph $w$ would no longer be a dead end: if we hit $w$, we're not stuck (we still have a chance to get back to where we want to be, by backtracking our steps). In the directed graph, $w$ is a dead end: once you hit $w$, you're done and you have no hope of making it to where you want to be.
• Thanks. Is there an example with no dead ends? does the following work: I take a binary tree graph and add edges from each leaf to the root? And if I want to find an example for $O(2^ \sqrt n)$ cover time? – JonyWalk Feb 22 '15 at 17:29
• Can you define a dead end precisely (in a mathematically precise way)? If I have two vertices $w,x$ with edges $w \to x$ and $x \to w$ and no other edges out of $w,x$, do you consider that a dead end? If not, it's trivial to adjust my example above accordingly. I don't know if your binary-tree-derived example has exponential cover time (I don't immediately see any reason why it should; I'd have guessed polynomial time is enough, but I haven't tried to calculate it). Anyway, this site is not good for follow-up questions/variants: we expect one question per post. – D.W. Feb 23 '15 at 5:55
• Ok thanks. I just wanted to see how I use your example to get the specific bound I asked about. I guess that if I connect such dead end vertices to every v_i where $i=c\cdot \sqrt n$ it would do. – JonyWalk Feb 23 '15 at 7:47