1
$\begingroup$

How can we find a walk with the minimal length starting from a vertex $v$, passing through all vertices and returning back to $v$?

We allow vertices and edges to be repeated along the walk. The length of a walk is the number of edges it has, counting repeated edges as many times as they appear.

I'm not sure if such a problem has been extensively studied. For example, our graph is the following graph; if we choose the start vertex $“1”$, then find the shortest distance from $“1”$ passing through all vertices and returning back to $“1”$.

![enter image description here

I have researched the Chinese Postman Problem and the Traveling Salesman Problem. They each have their own characteristics, but at first glance, they are different from my problem. The Chinese Postman Problem requires each edge to be traversed exactly once (i.e., edges cannot be repeated), while the Traveling Salesman Problem requires each vertex to be traversed exactly once (i.e., vertices cannot be repeated). My problem is more flexible. I'm not sure whether it can be reduced to these two problems.

If we directly apply the solution of the Traveling Salesman Problem, the following Maple solver will show that there is no traveling salesman tour. (To get back, we must repeat some vertices, such as the case where some vertices are cut vertices.)

with(GraphTheory):
G:=Graph({{1,5},{1,7},{1,10},{1,11},{2,10},{3,4},{3,10},
         {4,10}, {5,6},{5,7},{6,7},{7,8},{8,11},{8,13},{9,12},
         {10,11},{10,12},{11,12},{12,13}});
TravelingSalesman(G)
Out: infinity, []
$\endgroup$

1 Answer 1

1
$\begingroup$

What you are looking at is called "Hamiltonian walk". People have studied the problem of finding Hamiltonian walk extensively as seen with a google scholar search.

It is NP-hard to find a Hamiltonian walk in a given graph.

Here is brief proof of the NP-hardness.
We know that it is NP-hard to find a Hamiltonian cycle in a given cubic graph, since it is NP-complete to determine whether a Hamiltonian cycle exists in a cubic subgraphs of the square grid graph [1]. In a cubic graph, a Hamiltonian walk is the same as a Hamiltonian cycle. Hence it is NP-hard to find a Hamiltonian walk in a given cubic graph. Hence it is also NP-hard to find a Hamiltonian walk in a general graph.

$\endgroup$
4
  • 1
    $\begingroup$ Here is a shorter proof. A Hamiltonian walk of length $n$ is a Hamiltonian cycle, where $n$ is the number of vertices. Since it is NP-hard to find a Hamiltonian cycle, it is NP-hard to find a Hamiltonian walk. $\endgroup$
    – John L.
    May 12, 2023 at 5:53
  • $\begingroup$ Nice. This is exactly what I wanted to get. Thank you for informing me about this term “Hamiltonian walk”. I wonder if there are any standard algorithms to calculate these Hamiltonian walks. Most of softwares I know of tends to search for a Hamiltonian cycle rather than a Hamiltonian walk. (They have a fundamental difference.) $\endgroup$
    – licheng
    May 12, 2023 at 5:59
  • $\begingroup$ I apologize, I just noticed that you recommended some relevant resources. I will go and search for them again. $\endgroup$
    – licheng
    May 12, 2023 at 6:03
  • 1
    $\begingroup$ Great! I was checking them. I do not think I could do better than you, though. $\endgroup$
    – John L.
    May 12, 2023 at 6:07

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.