2
$\begingroup$

I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the nodes in the path is maximum). There's no restriction on what node the path starts or ends.

I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:

1)Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.

2)Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).

Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?

Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.

$\endgroup$
  • $\begingroup$ Trees don't have cycles, a path from a node to another node in a tree is unique as long as you are not allowing some redundant moves - visit a node and come back. $\endgroup$ – kelalaka Dec 17 '18 at 18:30
1
$\begingroup$

No, your algorithm does not work sometimes.

Here is a counterexample. Let graph $G$ have five weighted nodes, $A\mapsto 1$, $B\mapsto -1$, $C\mapsto 0$, $D\mapsto 1$, $E\mapsto 1$. There are four edges, $AB$, $BC$, $CD$ and $CE$.

Let us run your algorithm.

  1. Select node $B$ and run DFS($A$). We may get the maximum weight simple path $B, A$, whose weight is 0.
  2. Run DFS($A$), we may find the maximum weight simple path that starts at $A$, which is $A, B, C, D$, whose weight is 1. That path is returned.

However, the simple path with the maximum weight is actually $D,C,E$ whose weight is $2$.

$\endgroup$
  • $\begingroup$ @j_random_hacker Thanks, updated. $\endgroup$ – Apass.Jack May 17 at 19:51

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.