12
$\begingroup$

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.

$\endgroup$

1 Answer 1

14
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.