<p>If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard?</p>
<blockquote>
<p>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?</p>
</blockquote>

CC BY-SA 4.0
2020-11-23T07:35:47.790Z
This is called the chinese postman problem.
Laakeri
CC BY-SA 4.0
2020-11-23T09:31:20.623Z
And can be solved with min-cost flow, thanks
Sebastian Schmidt
CC BY-SA 4.0
2020-11-23T14:41:00.173Z
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).
Saeed
CC BY-SA 4.0
2020-11-23T14:57:44.863Z
*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 https://web.eecs.umich.edu/~pettie/matching/Edmonds-Johnson-chinese-postman.pdf
Saeed
<cc.complexity-theory><np-hardness><tsp>
Is the traveling salesman problem still NP-hard if all edges need to be covered as well?
Sebastian Schmidt
# Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

(Asked by: username_0 on 2020-11-23)

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?

**Tags:** cc.complexity-theory, np-hardness, tsp
> **Comments:**
> **username_1**: This is called the chinese postman problem.  
> **username_0**: And can be solved with min-cost flow, thanks  
> **username_2**: 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).  
> **username_2**: *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 https://web.eecs.umich.edu/~pettie/matching/Edmonds-Johnson-chinese-postman.pdf  

---

## 0 answers

