patternMinor
Examples for directed graphs with super polynomial cover time
Viewed 0 times
polynomialwithsupergraphsdirectedexamplestimeforcover
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#39668, answer score: 4
Revisions (0)
No revisions yet.