The Prize-Collecting TSP (PCTSP) is defined as the ordinary TSP with the difference that penalties are added to nodes; so we may avoid visiting a node paying its penalty, which is added to the overall cost. It currently admits a $2-\epsilon$ approximation ratio, where edge costs are considered to satisfy the triangle inequality. Obviously, ordinary TSP is PCTSP where all node penalties are set to inf.

I would like to ask, in the case a graph which does not satisfy the triangle inequality is chosen and ALL of its edges are deleted, replaced by 2 new edges connected to a 2-degree new node for each case of deleted edge, where each edge cost is equal to the deleted edge's cost/2 and having Euclidean distance equal to that (so the new graph is metric), don't we get a $(2-\epsilon)$ approximation ratio for the original (general and therefore non-approximable) graph? (Penalties for old nodes are set to inf and to new 2-degree nodes equal to 0).

Of course, there is a mistake in my thought, since this can't be true, so if somebody finds it, I would be pleased to listen to that. Thank you in priori.

  • 1
    $\begingroup$ It would be nice if you add a motivation part to your question and explain why you are interested in this question. $\endgroup$ – Kaveh Apr 18 '11 at 8:27
  • 1
    $\begingroup$ @Kaveh: Because it would prove that P = NP... $\endgroup$ – 5501 Apr 18 '11 at 10:38
  • 1
    $\begingroup$ @5501 that's not a motivation for this particular question. One of the aspects of writing good questions is explaining why you care about the question. $\endgroup$ – Suresh Venkat Apr 18 '11 at 16:01
  • 1
    $\begingroup$ Well I think it is obvious that I did not try to solve P=NP initially... $\endgroup$ – N27 Apr 18 '11 at 18:51
  • 1
    $\begingroup$ I just read a paper on PCTSP and have the curiosity on this issue, which continues to stay unexplained to me, btw. But, obviously, there is a flaw somewhere in my thought. $\endgroup$ – N27 Apr 19 '11 at 20:30

Edited may answer, I hope it becomes clearer now (or I find out what I did not understand):

Your process is as follows: If you have an edge $e = \{u,v\}$ with weight $t$ you replace $e$ by a path of length two with edges $\{u,z_e\}$ and $\{z_e,v\}$. $z_e$ is a new node and each of the two new edges get weight $t/2$. For each edge, we introduce a new node.

So far, we do not have a metric instance, because there is no edge between $u$ and $v$ so far and the distance between $u$ and $v$ is infinite. Therefore, you take the shortest path metric to get these distances. (I suppose that this is what you mean by "having Euclidean distances equal to that". Otherwise, you should clarify this.)

My point is that after adding distances according to the shortest path metric, the distance between $u$ and $v$ might not be $t$ anymore, so you do not get your original instance back: Consider a triangle with edge lengths $1$, $1$ and $t$. Let $u$ and $v$ be the nodes of the edge with weight $t$. Apply your construction. The shortest path between $u$ and $v$ is $2$ (it takes the four edges with weight $1/2$) and not $t$.

Btw: Euclidean distance should just be distance in the question.

  • $\begingroup$ I am not saying that. The 2 new edges have each cost t/2 but their costs are exactly equal to their distances. In other words, doing that for each one of the 3 triangle edges, creates a cycle of 6 vertices, where no 2 edges having a common endpoint are parallel to each other and where each edge's cost is equal to the edge's length. Or maybe I have misunderstood your statement and your talking about something else.. $\endgroup$ – N27 Apr 18 '11 at 11:15
  • $\begingroup$ But if you now take the metric completion, the shortest path from u to v does not take the two edges with weight t/2 but the four edges with weight 1/2. So you do not get your original graph back. $\endgroup$ – 5501 Apr 18 '11 at 11:48
  • $\begingroup$ Maybe you did not understand what I am trying to do in my original question or I do not understand what you are trying to say. Anyway..! And also, what is a metric completion of a graph? I googled that and I get no results. $\endgroup$ – N27 Apr 18 '11 at 18:50
  • $\begingroup$ Tried to clarify my answer. I used "metric completion" as a synoymn for "taking the shortest path metric". Or don't you do that after subdividing edges? $\endgroup$ – 5501 Apr 18 '11 at 19:09

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.