<p>Two questions where I think you have remained unclear:</p>

<ul>
<li>Are there any assumptions on the weight function?</li>
<li>What exactly holds if $(x, y) \in R$?</li>
</ul>

<p>Ad 4: You break your desired invariant for $R$ here since the last node in $x$ does not necessarily occur in $w$ at all. Example: $x = abc, y=adc, z=adce, w=ae$
</p>

<p>I believe a worst-case instance might be the complete graph with $w(i,k) = 1$ for $i$ the starting node and all $k\neq i$, and $w(j, k) = 0$ for all $j,k \neq i$. Paths with more nodes will never remove those from earlier iterations so the tree is never shrunk at all, growing up to having $n!$ nodes.</p>

CC BY-SA 2.5
2010-12-10T11:43:56.387Z
@Raphael: Initially, I felt that weights must be non-negative in order for the algorithm to work, but now I'm suspecting that it's not necessary. However, for simplicity let's assume that the weights are non-negative.
Giorgio Camerani
CC BY-SA 2.5
2010-12-10T11:49:29.297Z
@Raphael: $(x,y) \in R$ means that the last node in path $x$ is reached with an overall cost which is higher than the overall cost used to reach the _same_ last node in path $y$. So $x$ has to be preferred, since it's more costly.
Giorgio Camerani
CC BY-SA 2.5
2010-12-10T11:57:31.227Z
@Raphael: I've edited the question a bit: $p_t$ is the path from $T$'s root to $v_t$, not from $v_t$ to $T$'s root (as previously stated). I'm reasoning on the further parts of your answer.
Giorgio Camerani
CC BY-SA 2.5
2010-12-10T12:08:16.223Z
Ok, please see updated comment regarding step 4 above.
Raphael
CC BY-SA 2.5
2010-12-10T13:19:37.490Z
@Raphael: Yes you're right, I had exactly the same thought while I was at launch. The problem is that the term "transitive closure" is inappropriate for $R'$. Let's say instead that we build a new relation $Q$ from $R$, where $Q$ has nothing to do with the transitive closure of $R$. $Q$ contains $R$, plus those couples obtained through the above rule. Note: $Q$ is needed for correctness, since it avoids eliminating subtrees that must not be eliminated (because their elimination can lead to a non-optimal $W$).
Giorgio Camerani
CC BY-SA 2.5
2010-12-10T13:50:19.460Z
@Raphael: The worst-case instance you indicated indeed makes $T$ growing too much. I think the algorithm can be fixed (at least in this case) by putting in $R$ also those pairs $(x,y)$ such that $x$ has the same cost as $y$ (so just $\geq$ instead of $\gt$), and by never comparing twice the same pair of paths (i.e. now the algorithm compares $x$ to see if its cost is greater than $y$'s, and later it compares $y$ to see if its cost is greater than $x$'s: there must be only one $\geq$ comparison for each pair $(x,y)$: if $x \geq y$ we put $(x,y)$ in $R$, otherwise we put $(y,x)$ in $R$).
Giorgio Camerani
CC BY-SA 2.5
2010-12-10T19:55:22.100Z
If I now add another edge "far from" $i$ with cost $1$, you will reject partial paths that might later profit from this weight (and thus become optimal) early on because they are not better, aren't you?
Raphael
CC BY-SA 2.5
2010-12-11T09:41:45.443Z
@Raphael: Let me thank you for your interest. What do you mean by "add"? Wasn't the graph complete? I've tried a complete graph with $7$ nodes, built as indicated in your answer (and where $i = 1$). Then I've changed the weight of $(v_3,v_5)$ from $0$ to $1$, and it still works. In general, the algorithm _should_ reject a partial path $p$ only when it becomes clear that $p$ doesn't occur in none of the $n-1$ optimal paths returned in output (while such a conclusion can't be drawn, $p$ is kept). Did you find a counterexample on which the algorithm clearly fails?
Giorgio Camerani
CC BY-SA 2.5
2010-12-11T09:59:16.877Z
I did indeed mean to add another non-zero weight as you did. I have to admint that I never executed your algorithm but came up with the instance by gut feeling. Before I think further about it, I'd like to know: are you unsure about your algorithm's correctness or do you want to get an idea of its runtime?
Raphael
CC BY-SA 2.5
2010-12-11T10:24:13.673Z
@Raphael: I'm just a bit unsure about its correctness, let me say that I feel it should be correct, since it discards paths only when they are unequivocally sub-optimal (I've not a proof of this claim). On the other hand, I'm much more unsure about the size of $T$: I'm still afraid $T$ may grow superpolinomially on certain pathological instances. For what concerns running time: I didn't made a precise analysis yet, but it seems clearly polynomial _assuming that $T$ remains polynomially sized_.
Giorgio Camerani
CC BY-SA 2.5
2010-12-11T10:36:09.403Z
Well, if you are certain of its correctness the next logical step would be developing an actual proof. I imagine this should not be too difficult provided you can prove your desired invariant. If not, you might stumble over the reason it fails. As for runtime: If you never reject a path you can not certainly exclude as being shorter in the end, you will build all paths of length $n-1$ in the complete graph whith all weights equal, that is $(n-1)!$ many.
Raphael
CC BY-SA 2.5
2010-12-13T10:09:25.277Z
@Raphael: The algorithm fails on the complete graph with all weights equal. The problem seems not the size of $T$, but rather the correctness: at the end, only those nodes appearing as leaves of $T$ have maximum weight paths; those nodes appearing internally in $T$ are not guaranteed to be on their optimal path. I'm trying to figure out how to fix this.
Giorgio Camerani
CC BY-SA 2.5
2010-12-14T15:37:09.573Z
You have decided it is unfixable?
Raphael
CC BY-SA 2.5
2010-12-22T14:44:42.333Z
@Raphael: I'm still unable to tell whether it is unfixable or not, although it seems it is. What I know is that I'm unreasonable, obsessive and "thick as a brick", so I'll continue fighting with it in my spare time.
Giorgio Camerani
CC BY-SA 2.5
2011-01-01T16:55:15.453Z
Sad to hear that overzealous practises have now resulted in the first (?) casualty. I would not take most comments you received to heart. Good luck, anyway.
Raphael
CC BY-SA 2.5
2011-01-29T16:48:48.460Z
@Raphael: Thanks, expecially for your help, patience, and curiosity (and humbleness I would also say).
Giorgio Camerani
CC BY-SA 2.5
2011-01-29T17:09:35.350Z
You are very welcome.
Raphael
CC BY-SA 2.5
2010-12-10T11:15:45.800Z
2010-12-10T12:07:58.283Z
2010-12-10T12:07:58.283Z
Raphael
<p><strong>EDIT Dec 14th 2010<br></strong>
The algorithm is not correct: it's not the case that it always returns the optimal $W$.
<hr>
While reasoning on <a href="https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-in-weighted-graph">this</a> and other similar questions, I've sketched an algorithm that, given an undirect weighted graph $G=(V,E)$ of $n$ vertices and a vertex $v_i \in V$, returns an array $W$ of $n$ weights, where each $W_j$ (with $j \in [1,n]$) is the weight of the path of maximum weight from $v_i$ to $v_j$. Something must be wrong with the algorithm, but so far I couldn't figure out what. The algorithm seems correct at first sight, maybe its flaw is that the labeled tree $T$ it builds (see below) grows exponentially in size (I didn't yet implement it to see what happens).</p>

<p>Other than its input, the algorithm uses two further objects:</p>

<ol>
<li>A labeled tree $T$, which is initially composed by only one node whose label is $i$ (such node will be $T$'s root)</li>
<li>A relation $R \subseteq D^2$. $D$ is the domain of "paths without repetition", and $R(x,y)$ means "path $x$ removes path $y$". $R$ is initially the empty set.</li>
<li>A relation $Q \subseteq D^2$. $Q$ is built from $R$. $Q$ is initially the empty set.</li>
</ol>

<p>The algorithm operates as follows:</p>

<ol>
<li>For each leaf $v_k$ of $T$, add to it one new child node labeled $c$ for each $v_c \in V$ such that $\{ v_k, v_c \} \in E$ and there isn't any node labeled $c$ in the path in $T$ from $v_k$ to the root.</li>
<li>If $T$ changed during Step 1, go to Step 3. Else, go to Step 7.</li>
<li>Given a generic node $v_t$ of $T$, let $p_t$ be the path in $T$ from the root to $v_t$, let $w_t$ be the weight of $p_t$, and let $l_t$ be the label of $v_t$. Let $V(l)$ be the set of nodes of $T$ whose label is $l$. Now for each <i>different</i> label $l_k$ appearing in a leaf of $T$, let $V_2(l_k)$ be the set of all those subsets of $V(l_k)$ having cardinality $2$; for each $\{v_{k_1}, v_{k_2}\} \in V_2(l_k)$, if $w_{k_1} \geq w_{k_2}$ then add $(p_{k_1}, p_{k_2})$ to $R$, else add $(p_{k_2}, p_{k_1})$ to $R$.</li>
<li>Compute the relation $Q$ as follows: $Q$ contains all the couples of $R$, plus those obtained according to the following rule: if $(x, y) \in Q$ and $(z, w) \in Q$ and $y$ is a prefix of $z$, then $(x, w) \in Q$.</li>
<li>For each $y$ such that $\exists x (x, y) \in Q$, if $\not \exists z (z, y) \in Q$ such that $y$ is a prefix of $z$, then remove from $T$ the subtree whose root $r$ has a path from $T$'s root to $r$ equal to $y$.</li>
<li>Set both $R$ and $Q$ equal to the empty set. If $T$ changed during Step 5, then go to Step 3. Else, go to Step 1.</li>
<li>Set $W_j = 0, \forall j \in [1,n]$. Visit the tree $T$: for each visited $v_t$, if $w_t &gt; W_{l_t}$, set $W_{l_t} = w_t$. Return $W$.</li>
</ol>

<blockquote>
  <p><strong>Question(s)</strong>  </p>
  
  <ol><li>Is the algorithm correct?</li>  
  <li>Where is it flawed?</li>  
  <li>Is there an instance such that $T$ has exponentially many leaves?</li></ol>
</blockquote>

<p>Apologies in advance if this algorithm turns out to be completely uninteresting and naive.</p>

CC BY-SA 2.5
2010-12-15T23:16:01.150Z
I do not think that it is appropriate on this site to describe an algorithm and ask others to check its correctness.  Specifically, I am afraid of other people starting to post similar “I may have found a poly-time algorithm for an NP-complete problem, please point out its error” questions.  Voted to close as off topic.
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T08:51:58.767Z
I agree with Tsuyoshi on this one. Walter, maybe a discussion on meta would clarify whether such questions are appropriate.
Suresh Venkat
CC BY-SA 2.5
2010-12-16T10:02:02.980Z
I do not know what kind of research you guys do, but this seems to be a typical question that can come up. If we forbid low-level as well as this type of question, all we are left with is asking for references and big-picture.
Raphael
CC BY-SA 2.5
2010-12-16T13:18:51.700Z
@Raphael: Even if it is typical to come up with a “proof” of P=NP, I believe that asking others to check its correctness is inappropriate here.  And I hope that your assertion that “If we forbid low-level as well as this type of question, all we are left with is asking for references and big-picture” is false.  If it were true, that would only mean that this site is not interesting (at least to me).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T13:20:00.420Z
I posted a policy proposal related to this question on [Meta](http://meta.cstheory.stackexchange.com/questions/822/a-policy-proposal-against-questions-asking-for-a-correctness-check).
Tsuyoshi Ito
CC BY-SA 2.5
2010-12-16T13:40:55.120Z
I understand that it is accepted practice to ask colleagues if you get stuck. This kind of situation is imho enough motivation for a valid question here. And you are certainly right, the site would be boring if my assertion were right. But just look at the questions today. Most are already of the "boring" form.
Raphael
<ds.algorithms><graph-theory><graph-algorithms>
Algorithm for Longest Path in Undirected Weighted Graph
Giorgio Camerani
# Algorithm for Longest Path in Undirected Weighted Graph

(Asked by: username_0 on 2010-12-10)

**EDIT Dec 14th 2010**
The algorithm is not correct: it's not the case that it always returns the optimal $W$.

---

While reasoning on [this](https://cstheory.stackexchange.com/questions/3684/max-non-overlapping-path-in-weighted-graph) and other similar questions, I've sketched an algorithm that, given an undirect weighted graph $G=(V,E)$ of $n$ vertices and a vertex $v\_i \in V$, returns an array $W$ of $n$ weights, where each $W\_j$ (with $j \in [1,n]$) is the weight of the path of maximum weight from $v\_i$ to $v\_j$. Something must be wrong with the algorithm, but so far I couldn't figure out what. The algorithm seems correct at first sight, maybe its flaw is that the labeled tree $T$ it builds (see below) grows exponentially in size (I didn't yet implement it to see what happens).

Other than its input, the algorithm uses two further objects:

1. A labeled tree $T$, which is initially composed by only one node whose label is $i$ (such node will be $T$'s root)
2. A relation $R \subseteq D^2$. $D$ is the domain of "paths without repetition", and $R(x,y)$ means "path $x$ removes path $y$". $R$ is initially the empty set.
3. A relation $Q \subseteq D^2$. $Q$ is built from $R$. $Q$ is initially the empty set.

The algorithm operates as follows:

1. For each leaf $v\_k$ of $T$, add to it one new child node labeled $c$ for each $v\_c \in V$ such that $\{ v\_k, v\_c \} \in E$ and there isn't any node labeled $c$ in the path in $T$ from $v\_k$ to the root.
2. If $T$ changed during Step 1, go to Step 3. Else, go to Step 7.
3. Given a generic node $v\_t$ of $T$, let $p\_t$ be the path in $T$ from the root to $v\_t$, let $w\_t$ be the weight of $p\_t$, and let $l\_t$ be the label of $v\_t$. Let $V(l)$ be the set of nodes of $T$ whose label is $l$. Now for each *different* label $l\_k$ appearing in a leaf of $T$, let $V\_2(l\_k)$ be the set of all those subsets of $V(l\_k)$ having cardinality $2$; for each $\{v\_{k\_1}, v\_{k\_2}\} \in V\_2(l\_k)$, if $w\_{k\_1} \geq w\_{k\_2}$ then add $(p\_{k\_1}, p\_{k\_2})$ to $R$, else add $(p\_{k\_2}, p\_{k\_1})$ to $R$.
4. Compute the relation $Q$ as follows: $Q$ contains all the couples of $R$, plus those obtained according to the following rule: if $(x, y) \in Q$ and $(z, w) \in Q$ and $y$ is a prefix of $z$, then $(x, w) \in Q$.
5. For each $y$ such that $\exists x (x, y) \in Q$, if $\not \exists z (z, y) \in Q$ such that $y$ is a prefix of $z$, then remove from $T$ the subtree whose root $r$ has a path from $T$'s root to $r$ equal to $y$.
6. Set both $R$ and $Q$ equal to the empty set. If $T$ changed during Step 5, then go to Step 3. Else, go to Step 1.
7. Set $W\_j = 0, \forall j \in [1,n]$. Visit the tree $T$: for each visited $v\_t$, if $w\_t > W\_{l\_t}$, set $W\_{l\_t} = w\_t$. Return $W$.

> **Question(s)**
>
> 1. Is the algorithm correct?
> 2. Where is it flawed?
> 3. Is there an instance such that $T$ has exponentially many leaves?

Apologies in advance if this algorithm turns out to be completely uninteresting and naive.

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: I do not think that it is appropriate on this site to describe an algorithm and ask others to check its correctness.  Specifically, I am afraid of other people starting to post similar “I may have found a poly-time algorithm for an NP-complete problem, please point out its error” questions.  Voted to close as off topic.  
> **username_2**: I agree with Tsuyoshi on this one. Walter, maybe a discussion on meta would clarify whether such questions are appropriate.  
> **username_3**: I do not know what kind of research you guys do, but this seems to be a typical question that can come up. If we forbid low-level as well as this type of question, all we are left with is asking for references and big-picture.  
> **username_1**: @username_3: Even if it is typical to come up with a “proof” of P=NP, I believe that asking others to check its correctness is inappropriate here.  And I hope that your assertion that “If we forbid low-level as well as this type of question, all we are left with is asking for references and big-picture” is false.  If it were true, that would only mean that this site is not interesting (at least to me).  
> **username_1**: I posted a policy proposal related to this question on [Meta](http://meta.cstheory.stackexchange.com/questions/822/a-policy-proposal-against-questions-asking-for-a-correctness-check).  
> **username_3**: I understand that it is accepted practice to ask colleagues if you get stuck. This kind of situation is imho enough motivation for a valid question here. And you are certainly right, the site would be boring if my assertion were right. But just look at the questions today. Most are already of the "boring" form.  

---

## 1 answers

### Answer by username_3 on 2010-12-10. Score: 1 | Accepted answer

Two questions where I think you have remained unclear:

* Are there any assumptions on the weight function?
* What exactly holds if $(x, y) \in R$?

Ad 4: You break your desired invariant for $R$ here since the last node in $x$ does not necessarily occur in $w$ at all. Example: $x = abc, y=adc, z=adce, w=ae$

I believe a worst-case instance might be the complete graph with $w(i,k) = 1$ for $i$ the starting node and all $k\neq i$, and $w(j, k) = 0$ for all $j,k \neq i$. Paths with more nodes will never remove those from earlier iterations so the tree is never shrunk at all, growing up to having $n!$ nodes.

> **Comments:**
> **username_0**: @username_3: Initially, I felt that weights must be non-negative in order for the algorithm to work, but now I'm suspecting that it's not necessary. However, for simplicity let's assume that the weights are non-negative.  
> **username_0**: @username_3: $(x,y) \in R$ means that the last node in path $x$ is reached with an overall cost which is higher than the overall cost used to reach the _same_ last node in path $y$. So $x$ has to be preferred, since it's more costly.  
> **username_0**: @username_3: I've edited the question a bit: $p_t$ is the path from $T$'s root to $v_t$, not from $v_t$ to $T$'s root (as previously stated). I'm reasoning on the further parts of your answer.  
> **username_3**: Ok, please see updated comment regarding step 4 above.  
> **username_0**: @username_3: Yes you're right, I had exactly the same thought while I was at launch. The problem is that the term "transitive closure" is inappropriate for $R'$. Let's say instead that we build a new relation $Q$ from $R$, where $Q$ has nothing to do with the transitive closure of $R$. $Q$ contains $R$, plus those couples obtained through the above rule. Note: $Q$ is needed for correctness, since it avoids eliminating subtrees that must not be eliminated (because their elimination can lead to a non-optimal $W$).  
> **username_0**: @username_3: The worst-case instance you indicated indeed makes $T$ growing too much. I think the algorithm can be fixed (at least in this case) by putting in $R$ also those pairs $(x,y)$ such that $x$ has the same cost as $y$ (so just $\geq$ instead of $\gt$), and by never comparing twice the same pair of paths (i.e. now the algorithm compares $x$ to see if its cost is greater than $y$'s, and later it compares $y$ to see if its cost is greater than $x$'s: there must be only one $\geq$ comparison for each pair $(x,y)$: if $x \geq y$ we put $(x,y)$ in $R$, otherwise we put $(y,x)$ in $R$).  
> **username_3**: If I now add another edge "far from" $i$ with cost $1$, you will reject partial paths that might later profit from this weight (and thus become optimal) early on because they are not better, aren't you?  
> **username_0**: @username_3: Let me thank you for your interest. What do you mean by "add"? Wasn't the graph complete? I've tried a complete graph with $7$ nodes, built as indicated in your answer (and where $i = 1$). Then I've changed the weight of $(v_3,v_5)$ from $0$ to $1$, and it still works. In general, the algorithm _should_ reject a partial path $p$ only when it becomes clear that $p$ doesn't occur in none of the $n-1$ optimal paths returned in output (while such a conclusion can't be drawn, $p$ is kept). Did you find a counterexample on which the algorithm clearly fails?  
> **username_3**: I did indeed mean to add another non-zero weight as you did. I have to admint that I never executed your algorithm but came up with the instance by gut feeling. Before I think further about it, I'd like to know: are you unsure about your algorithm's correctness or do you want to get an idea of its runtime?  
> **username_0**: @username_3: I'm just a bit unsure about its correctness, let me say that I feel it should be correct, since it discards paths only when they are unequivocally sub-optimal (I've not a proof of this claim). On the other hand, I'm much more unsure about the size of $T$: I'm still afraid $T$ may grow superpolinomially on certain pathological instances. For what concerns running time: I didn't made a precise analysis yet, but it seems clearly polynomial _assuming that $T$ remains polynomially sized_.  
> **username_3**: Well, if you are certain of its correctness the next logical step would be developing an actual proof. I imagine this should not be too difficult provided you can prove your desired invariant. If not, you might stumble over the reason it fails. As for runtime: If you never reject a path you can not certainly exclude as being shorter in the end, you will build all paths of length $n-1$ in the complete graph whith all weights equal, that is $(n-1)!$ many.  
> **username_0**: @username_3: The algorithm fails on the complete graph with all weights equal. The problem seems not the size of $T$, but rather the correctness: at the end, only those nodes appearing as leaves of $T$ have maximum weight paths; those nodes appearing internally in $T$ are not guaranteed to be on their optimal path. I'm trying to figure out how to fix this.  
> **username_3**: You have decided it is unfixable?  
> **username_0**: @username_3: I'm still unable to tell whether it is unfixable or not, although it seems it is. What I know is that I'm unreasonable, obsessive and "thick as a brick", so I'll continue fighting with it in my spare time.  
> **username_3**: Sad to hear that overzealous practises have now resulted in the first (?) casualty. I would not take most comments you received to heart. Good luck, anyway.  
> **username_0**: @username_3: Thanks, expecially for your help, patience, and curiosity (and humbleness I would also say).  
> **username_3**: You are very welcome.  

---

