Suppose I have a weighted connected graph which is traversable (each vertex has even degree) and I wish to walk over all edges. Clearly any Eulerian path minimizes the total weight. What can be said about the case of non-traversable (weighted connected) graphs? Can a minimum-weight path still be found in polynomial time?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Yes, this can be done in polynomial time.
What we need to is find a minimum-weight set of edges to traverse twice, such that the graph with some edges doubled is traversable. Once we have that, finding an actual Eulerian path is of course easy.
The edges we need to double will form a set of paths each connecting two odd-degree nodes, such that each odd-degree node is the endpoint of exactly one of the path.
To find out which odd-degree nodes to connect, temporarily disregard the even-degree nodes and instead consider a graph with one edge between each pair of odd-degree nodes, its weight being the length of the shortest path between those nodes in the original graph.
What we need to find is then a minimal perfect matching in the reduced graph, which is known to have a polynomial-time algorithm.