1
$\begingroup$

I am working with undirected unweighted graphs, and I am searching for an algorithm that gives me a spanning tree minimizing the number of moves to visit every nodes.

For example, given this graph :

enter image description here

one spanning tree may be :

enter image description here

but, starting at a, 11 moves are necessary to go through every nodes : ab, ba, ah, hg, gh, hi, ic, cd, dc, cf, fe (note that getting back to the start is not required). But with another tree such as this one :

enter image description here

only 8 moves are necessary (which is incidentally the lowest possible for a graph with 9 nodes, but this is not attainable in every graph e.g. if there are multiple "dead-ends").

I am looking for an algorithm which could output such a tree (or path), or at least a good approximation. The graphs I am working with may have up to 100 nodes.

One of my ideas was to generate every spanning tree and then find the best one, but I don't know how to do it, and the number of trees may grow too fast for this to be practical.

$\endgroup$

2 Answers 2

2
$\begingroup$

The problem is NP-hard since the graph admits a spanning tree with no backtracking if and only if it contains a Hamiltonian path. This shows that, if the measure to optimize is the number of times you backtrack, then there can be no polynomial-time approximation algorithm unless $P \neq NP$.

If the measure is the number of moves needed to visit all the vertices while moving along the edges of the tree, then an arbitrary spanning tree already provides a $2$-approximation. Indeed, any solution must involve at least $n-1$ moves, while an Eulerian tour of a spanning tree traverses each of the $n-1$ edges twice.

$\endgroup$
0
$\begingroup$

Thanks to this post, I found a solution :

  1. Use the Floyd-Warshall algorithm on my graph to get the matrix of the shortest distance between every nodes
  2. Apply a TSP solver on this to get the shortest path.

Unfortunately, this means the complexity is $O(n^22^n+n^3)$ at best (when using a dynamic programming approach).

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