3
$\begingroup$

I have a graph G with $n$ nodes. I am looking for a finite sequence $i_1, i_2, i_3, \dots, i_m$ such that

  1. The sequence covers every vertex of the graph ($\forall 1\le j\le n: \exists k: i_k=j$)

  2. Neighboring vertices in the sequence are connected ($\forall j: (V_{i_j},V_{i_{j+1}}) \in G$)

I would also like this sequence to be pretty short (small $m$)--as short as possible would be nice, but not necessary. What reasonably efficient algorithm exists for this problem?

Whenever I search for information about this problem, I get lots of information on Hamiltonian paths. A Hamiltonian path, if it exists, would of course be the best solution to my problem. But it probably doesn't, since $G$ is pretty sparse (degrees typically around 2 to 5, in a graph with about 30,000 vertices).

So, I'm looking for some kind of optimization algorithm that will find a short path through the whole graph, which visits each node not too many times.

It seems like a natural problem that must be well-studied, but my Google skill is really failing me, so here I am. I'm not totally sure I'm on the right stack exchange for this (maybe computer science or statistics would be better) but here we are.

$\endgroup$
  • $\begingroup$ Do you know that the graph is connected? $\endgroup$ – paw88789 Oct 30 '17 at 16:49
  • 1
    $\begingroup$ I haven't checked yet. It may turn out not to be. However, if it isn't, I want to solve the same problem on each connected component, so we can assume a connected graph $G$. It just may not be as large as I said it was. $\endgroup$ – user54038 Oct 30 '17 at 18:01
  • 1
    $\begingroup$ This problem is known as graphic TSP if you're looking for references; see, for example, this paper. (Note that it's much more popular to look for a closed tour in which your last vertex is the same as the first, but the path version is also studied.) $\endgroup$ – Misha Lavrov Oct 30 '17 at 20:29
  • $\begingroup$ @MishaLavrov: The linked reference contains an algorithm of the kind I'm looking for, as well as references to several other, simpler ones. Therefore, this seems to me to be an answer to my question. Since it is a comment I can't accept it as an answer. However, since Especially Lime's answer was also very helpful and also provided an algorithm, I will accept that to close the question. $\endgroup$ – user54038 Nov 2 '17 at 15:45
4
$\begingroup$

You can do this in linear time for any connected graph if you're willing to have $m=2n-2$, which is certainly less than twice the optimal $m$. To do this, construct a spanning tree (e.g. by depth-first search) and take a route that traverses each edge of the spanning tree twice. Whenever you discover a vertex in DFS you move to that vertex; whenever you finish processing a vertex you go back along the edge you used to discover that vertex.

This gives a route which takes $2n-2$ steps (since there are $n-1$ edges in the tree), so $m=2n-1$, but since it starts and finishes in the same place you don't need the last step so can always do $m\leq 2n-2$. If your graph is a star, $m=2n-2$ is the best you can do.

This doesn't guarantee to visit every vertex a bounded number times, only that the average number of times a vertex is visited is less than $2$. However, the maximum number of times a vertex is visited is at most the maximum degree of the graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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