# complexity theory – Reduction from TSP to even TSP

I have a question from a test that I failed to pass, I failed to do the question.

the question:

Let’s look at the problem of the double-length traveling agent. Given graph $$G = (V,E)$$ and a weight function on the arcs of the graph $$W:E rightarrow mathbb{R} ^ {+}$$ we would like to find an easier route (of the routes of even length) that passes through all the vertices of the graph and ends at the vertex where it started. We will be interested in the decisive version of the problem. That is, given a natural number $$d$$, we are asked: “Is there such a double-length route weighing ≤ $$d$$?”

Formally:

$$ETSP =$${
$$left langle G,w,d right rangle$$ | There is a path of double length, which passes through all the vertices of G and ends at the point where it started and weighs ≤ $$d$$ }

Determine which of the following statements is correct:

1. The language is in P, since a polynomial algorithm can be constructed by passing all the neighbors at a distance of less than 6 from each vertex in G.
2. The language is in P, as a greedy polynomial algorithm can be constructed which will solve the problem. For each vertex, the algorithm will look at the neighbor with the minimum weight edge each time. This will ensure that the route that passes through all the vertices will be at a very small weight. Finally, he will check whether the length of the route is even, and if not – he will start again.
3. $$TSP leq _P ETSP$$ can be reduced so the language is in NPC
4. The language is not in NP, since if there is no such route then we can not verify it.
5. None of the above claims are true.

I think 3 is the correct answer.

1. Does not make sense
2. A greedy algorithm does not help with such problems
3. That’s the answer in my opinion, I’m not sure
4. I think it’s not true, you can check it in polynomial time, just go over the witness’ solution and see that it is even in length