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 even-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 an even-length route weighing ≤ $d$?"


$ETSP = ${ $\left \langle G,w,d \right \rangle$ | There is a path of even 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 bypassing 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
  • $\begingroup$ A more meaningful problem is only to allow complete graphs, otherwise it can be easily reduced from the Hamiltonian cycle problem $\endgroup$
    – xskxzr
    Jul 22 at 1:43
  • $\begingroup$ Sorry for my English, I meant an even-length path. In TSP you can have an odd and even length path. But in ETSP it is only possible even length path $\endgroup$
    – dust
    Jul 22 at 14:29
  • $\begingroup$ Just multiply all edge weights by $2$. $\endgroup$
    – Steven
    Jul 23 at 0:03

Option 1 is odd. We don't know whether a polynomial algorithm can be constructed. The "passing all the neighbors at a distance of less than 6 from each vertex in $G$" is unclear. Any algorithm solving the TSP problem must visit all vertices. Therefore it must also visit all neighbors of each vertex and, in particular, all neighbors at distance less than $6$. If a polynomial-time algorithm exists, the second part of option 1, as I read it, is trivially satisfied.

Regarding option $2$. It is unclear what "will look at the neighbor with the minimum weight edge each time" means. In particular, what is meant by look? If the algorithm is just required to examine that neighbor in some way then this condition becomes trivial to satisfy (since the algorithm is still free to pick whatever tour) but we don't know if the language is in $P$. If the algorithm is required to build a tour by iteratively going from the current vertex to its closest neighbor, then this algorithm could even not produce a valid tour. If the algorithm goes to the closest unvisted neighbor, then it produces a tour but doesn't ensure that the length is even nor minimized.

Option 3 is true. Simply multiply all edge weights (and the target upper bound on the tour length) by $2$ (or any positive even constant). Notice that the language is in NP since a certificate is the tour itself.

Option $4$ and $5$ are false (this is implied by the fact that option 3 is true).


Your Answer

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

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