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?

  • 5
    $\begingroup$ This is called the chinese postman problem. $\endgroup$
    – Laakeri
    Nov 23, 2020 at 7:35
  • 1
    $\begingroup$ And can be solved with min-cost flow, thanks $\endgroup$ Nov 23, 2020 at 9:31
  • 1
    $\begingroup$ 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). $\endgroup$
    – Saeed
    Nov 23, 2020 at 14:41
  • 2
    $\begingroup$ *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/… $\endgroup$
    – Saeed
    Nov 23, 2020 at 14:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.