Find the spanning tree minimizing the backtracking in an unweighted graph

Question

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 :

one spanning tree may be :

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 :

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.

Answer 1

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.

Answer 2

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