# How to find a "short" walk that visits all vertices of a strongly connected directed graph

I am interested in the following algorithmic problem: Given a strongly connected directed graph $$G$$, I want a "short" (see below for what I mean by short) walk that starts with an arbitrary vertex $$s$$ and contains all vertices of $$G$$.

Deciding if such a walk can be a path (i.e. no repeated vertices) is a well known NP-complete problem.

So I am interested in a walk that might repeat vertices.

I can perform the following: Start with the walk $$X=(s)$$ and, until there are unvisited vertices, let $$v$$ be unvisited, take the last vertex $$x$$ from $$X$$ and append a $$x$$-$$v$$ path (it must exist because $$G$$ is strongly connected) to $$X$$. This procedure will eventually terminate, but will produce a walk of possibly quadratic length.

My question is, can we do better and guarantee a linear-sized walk? Is there an efficient (say linear or maybe $$n\log n$$) algorithm to compute the walk?

What I know: if G was undirected (and connected), there is always a walk visiting each vertex and it can be easily found by computing the spanning tree and doing DFS traversal of it, but this is not applicable since we assume $$G$$ to be directed.

The answer is no. For any $$n\geq 3$$ consider an oriented cycle $$C_n$$ and let $$u\to v$$ be adjacent in the $$C_n$$. Create $$n$$ vertices $$x_1...x_n$$ and add edges $$u\to x_i$$ and $$x_i \to v$$. Now any walk containing all vertices has length $$\Omega(n^2)$$.