How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$?

The cover time is the expected length of a random walk that visits all vertices.

  • 4
    $\begingroup$ What is the "cover time"? $\endgroup$ – Raphael Jun 22 '12 at 14:57
  • $\begingroup$ I think cover time means the expected number of steps taken by a random walk to visit every vertex. $\endgroup$ – Juho Jun 22 '12 at 21:19
  • $\begingroup$ You also have to assume that the graph is strongly connected. $\endgroup$ – Yuval Filmus Jan 27 '13 at 6:38

You do it in two steps:

  1. First you think of a graph which you can expect to be difficult.

  2. Then you prove your suspicion.

Let's start with the first step - do you have any graph in mind?

  • 1
    $\begingroup$ To a novice, it might not be at all obvious that when you say “think of a graph”, you really mean “for all $n$ [or at least an infinite number of integers $n$], think of a graph of size $n$” and “prove your suspicion” involves computing the cover size in terms of $n$ and finding an expression that is exponential in $n$. A hint that isn't even didactic is really not useful. $\endgroup$ – Gilles 'SO- stop being evil' Jan 14 '15 at 19:13
  • $\begingroup$ @Gilles Why don't you add your own answer, then? $\endgroup$ – Yuval Filmus Jan 14 '15 at 20:01

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.