Algorithm to cover all edges given starting node

Question

Working on an algorithm for a game I am developing with a friend and we got stuck. Currently, we have a cyclic undirected graph, and we are trying to find the quickest path from starting node S that covers every edge. We are not looking for a tour and there can be repeated edges.

Any ideas on an algorithm or approximation? I'm sure this problem is NP-hard, but I don't believe it's TSP.

Answer 1

Route Inspection

This is known as the route inspection problem and it does have a polynomial solution.

The basic idea (see the link for more details) is that it is easy to solve for an Eulerian path (where we visit every edge once), but an Eulerian path is only possible for certain graphs.

In particular, a graph has to be connected and have either 0 or 2 vertices of odd degree.

However, it is possible to generalise this for other graphs by adding additional edges in the cheapest way that will produce a graph that does have an Eulerian path. (Note that we have added more edges so we may travel multiple times over edges in the original graph.)

The way of choosing the best way to add additional edges is a maximal matching problem that can be solved in O(n^3).

P.S.

Concidentally I wrote a simple demo earlier today (link to game) for a planar max-cut problem. The solution to this turns out to be based on exactly the same route inspection problem :)

EDIT

I just spotted from the comments that in your particular case your graph may be a tree.

If so, then I believe the answer is much simpler as you just need to do a DFS over the tree making sure to visit the shallowest subtree first.

For example, suppose you have a tree with edges S->A and S->A->B. S has two subtrees, and you should visit A first because it is shallower.

The total edges visited will equal the number of edges visited in a full DFS, minus the depth of the last leaf visited, which is why to minimise the total edges you want to maximise the depth of the last leaf, and hence visit the shallowest subtree first.