Given a $n$ vertices $m$ edges connected graph $G$ and a source vertex $x$, I start a random walk from $x$ until it discovered $a$ vertices for some small $a$ ($< n^{1/4}$). What is the expected time required to discover $a$ different vertices?
The cover time $C$ answers this question when $a=n$. Alelitinas, Karp, Lipton, Lovasz and Rackoff showed that $\mathbb{E}[C] \le O(n^3)$ for general undirected graphs, and Broder and Karlin improved the bound to $\mathbb{E}[C] \le O(\frac{n\log n}{1-\lambda_2})$ where $\lambda_2$ is the second largest eigenvalue of the adjacency matrix of $G$.
This lead to the conjecture that for a random walk to discover $a$ vertices on a undirected graph, one need to make, in expectation, less than $a^3$ steps. In undirected graphs, using the reversibility of the random walk on $G$, I believe the same argument as AKLLR can be used to prove this conjecture.
However, I need this to work on an strongly connected directed graph. Intuitively, it seems that the cover time of such a graph should be bounded by the cover time of its undirected version because directions on the edges prevent the possibility of zigzagging on a few edges. Is it true? It feels like this is something that should be known but random walks don't behave as well on digraphs as they do on undirected graphs. In their paper AKLLR show it works for Eulerian digraphs (ones where the in-degree equals the out-degree), unfortunately I can't make this assumption.
Does anyone know about such a result?