4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – JonyWalk Feb 22 '15 at 17:29
  • $\begingroup$ 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. $\endgroup$ – D.W. Feb 23 '15 at 5:55
  • $\begingroup$ 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. $\endgroup$ – JonyWalk Feb 23 '15 at 7:47

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.