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

<p>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.</p>

<p>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.)</p>

<p>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$.</p>

<p>Btw: Euclidean distance should just be distance in the question. </p>

CC BY-SA 3.0
2011-04-18T11:15:31.053Z
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..
N27
CC BY-SA 3.0
2011-04-18T11:48:01.317Z
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.
5501
CC BY-SA 3.0
2011-04-18T18:50:15.777Z
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.
N27
CC BY-SA 3.0
2011-04-18T19:09:06.807Z
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?
5501
CC BY-SA 3.0
2011-04-18T10:42:21.867Z
2011-04-18T19:18:03.947Z
2011-04-18T19:18:03.947Z
5501
<p>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.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2011-04-18T08:27:12.950Z
It would be nice if you add a motivation part to your question and explain why you are interested in this question.
Kaveh
CC BY-SA 3.0
2011-04-18T10:38:12.340Z
@Kaveh: Because it would prove that P = NP...
5501
CC BY-SA 3.0
2011-04-18T16:01:45.870Z
@5501 that's not a motivation for *this* particular question. One of the aspects of [writing good questions](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) is explaining why **you** care about the question.
Suresh Venkat
CC BY-SA 3.0
2011-04-18T17:43:30.913Z
@Suresh: I'm sorry, my comment was supposed to have an ironic undertone (which, I learnt, is not suitable for the internet). I do not think that you need to motivate TSP and if the reasoning in the question were true, then P = NP would follow (which is noticed by N27, too).
5501
CC BY-SA 3.0
2011-04-18T18:27:52.727Z
apologies: sometimes I inhabit the literalverse ;)
Suresh Venkat
CC BY-SA 3.0
2011-04-18T18:51:41.440Z
Well I think it is obvious that I did not try to solve P=NP initially...
N27
CC BY-SA 3.0
2011-04-18T19:16:43.697Z
Sure, I understood this. You are trying to find the flaw in your thoughts above. (And I will never do ironic statements again ;-))
5501
CC BY-SA 3.0
2011-04-19T04:32:15.507Z
@5501, your comment is not helpful in this case. The motivation of OP for a question is important on cstheory. E.g. if the question is motivated by an application then we should add the corresponding tag, if it is not and it is also not related to research then it maybe off-topic for this site I may close it. If it is a (veiled) attempt to solve a famous open question then it may need to be closed. Also motivation can help others answer the question. In short, it is not unusual here to ask the OP to provide motivation and background for his/her question.
Kaveh
CC BY-SA 3.0
2011-04-19T04:34:04.800Z
@N27, could you please tell us why you are interested in this particular question?
Kaveh
CC BY-SA 3.0
2011-04-19T20:30:46.323Z
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.
N27
CC BY-SA 3.0
2011-04-20T20:55:11.227Z
I still think that either your graph is not complete (and therefore the instance is not metric) or you calculate the distances in a wrong way when making it complete. If you are still interested, you maybe want to describe your construction in a more detailed way? Perhaps I do not understand your construction correctly.
5501
CC BY-SA 3.0
2011-04-26T02:23:30.547Z
Thanks N27, it would be nice if you add a link to the paper and state the motivation inside the post. ps: take a look at this meta post for future reference: [How to ask a good question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question)
Kaveh
<ds.algorithms><approximation-algorithms><tsp>
Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP
N27
# Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP

(Asked by: username_0 on 2011-04-18)

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.

**Tags:** ds.algorithms, approximation-algorithms, tsp

> **Comments:**
> **username_1**: It would be nice if you add a motivation part to your question and explain why you are interested in this question.  
> **username_2**: @username_1: Because it would prove that P = NP...  
> **username_3**: @username_2 that's not a motivation for *this* particular question. One of the aspects of [writing good questions](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) is explaining why **you** care about the question.  
> **username_2**: @Suresh: I'm sorry, my comment was supposed to have an ironic undertone (which, I learnt, is not suitable for the internet). I do not think that you need to motivate TSP and if the reasoning in the question were true, then P = NP would follow (which is noticed by username_0, too).  
> **username_3**: apologies: sometimes I inhabit the literalverse ;)  
> **username_0**: Well I think it is obvious that I did not try to solve P=NP initially...  
> **username_2**: Sure, I understood this. You are trying to find the flaw in your thoughts above. (And I will never do ironic statements again ;-))  
> **username_1**: @username_2, your comment is not helpful in this case. The motivation of OP for a question is important on cstheory. E.g. if the question is motivated by an application then we should add the corresponding tag, if it is not and it is also not related to research then it maybe off-topic for this site I may close it. If it is a (veiled) attempt to solve a famous open question then it may need to be closed. Also motivation can help others answer the question. In short, it is not unusual here to ask the OP to provide motivation and background for his/her question.  
> **username_1**: @username_0, could you please tell us why you are interested in this particular question?  
> **username_0**: 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.  
> **username_2**: I still think that either your graph is not complete (and therefore the instance is not metric) or you calculate the distances in a wrong way when making it complete. If you are still interested, you maybe want to describe your construction in a more detailed way? Perhaps I do not understand your construction correctly.  
> **username_1**: Thanks username_0, it would be nice if you add a link to the paper and state the motivation inside the post. ps: take a look at this meta post for future reference: [How to ask a good question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question)  

---

## 1 answers

### Answer by username_2 on 2011-04-18. Score: 1

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.

> **Comments:**
> **username_0**: 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..  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_2**: 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?  

---

