Given an unweighted graph $G$. Here are some definitions that I invented:
- A walk $W$ is called a spanning walk if $v \in V(G) \implies v\in V(W)$
- A $(u,v)$-walk $W$ is a walk of the form $u=v_0, v_0v_1, \cdots, v_{t-1}v_{t}, v_{t}=v$
Design an algorithm that finds the length of a shortest spanning $(u,v)$-walk.
This is a question I made for myself. However, I was not able to find an efficient algorithm. I tried to use DP but since walks may have repeated edges, there is no nice topological order to the structure of subproblems. Hence, the solution I discovered was to use backtracking that restricts duplicated arcs, rather than duplicated vertices in the standard application. Unfortunately, it is a quite inefficient alogrithm despite its correctness. I would like to know whether this problem is $NP$-complete; otherwise, please give me an efficient algorithm.
Well, in particular, there is a spanning $(u,v)$-walk of length $|V(G)|-1$ if and only if there is a Hamiltonian path from $u$ to $v$. The Hamiltonian path problem is NP-complete; therefore, so is this problem.