Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
You want a path that traverses every edge at least once, I suppose? –  Henning Makholm Oct 7 '13 at 22:57
    
@HenningMakholm: Yes. Sorry, I had typed that but it must have been deleted as I edited the post before submitting. –  Charles Oct 8 '13 at 3:46
    
I would be surprised if it had an efficient solution. It is a variant of the travelling purchaser problem (on the line graph) but with some simplifications (like travel cost zero) and only one product. –  Leen Droogendijk Oct 8 '13 at 5:58
1  
This is the Route inspection problem a.k.a. Chinese Postman Problem. This has a polynomial time algorithm for undirected graphs and polynomial for directed graphs, but it is NP-complete for mixed graphs. –  N. S. Oct 8 '13 at 17:10

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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