# Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard?

Given a graph G with non-negative edge weights, is there a circular walk in G that covers all edges and has weight at most t?

• This is called the chinese postman problem. Nov 23, 2020 at 7:35
• And can be solved with min-cost flow, thanks Nov 23, 2020 at 9:31
• You actually want to find an eulerian tour which is polynomial-time solvable. The only issue is that you may have odd degree vertices and this as Laakeri said is the Chinese postman problem. For this, construct a complete graph that its nodes are those odd degree vertices and edge weights are the shortest path distances between them. Then find a matching here and add this matching to the original graph (by maybe adding parallel edges), an eulerian tour here, would be a solution to your problem (just unfold it). Nov 23, 2020 at 14:41
• *I had to write a minimum size maximal matching which should be clear from the context but, I've forgotten to write it in the previous comment. Also why this intuitive algorithm actually works is explained in the original paper of Edmonds and Johnson web.eecs.umich.edu/~pettie/matching/… Nov 23, 2020 at 14:57