7
$\begingroup$

I have a tree where each edge 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 edges 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$
3
$\begingroup$

Good idea. In fact, if all the edge weights are 1, this is a standard way to find the diameter of a tree. Unfortunately, your two-DFS algorithm has a problem when the edge weights can be negative.

Consider, for example, the following edge-weighted tree:

enter image description here

If we do a DFS starting at $u=v_0$ we find that there are two maximal paths from $u$: to $v_1$ and to $v_3$, both with weight 2. Doing the second DFS from $v_1$ yields the maximal path $\langle v_1, v_0, v_2, v_3\rangle$ of weight 4, but doing the DFS from $v_3$ gives the maximal path $\langle v_3, v_2, v_4\rangle$ which has weight 5.

I'm fairly sure you could modify your algorithm so that it gives a maximal path, but I suspect that the modified version would no longer be linear in the number of vertices. Gotta think about that.

$\endgroup$
5
$\begingroup$

Consider the following algorithm, where we start at terminal nodes and keep removing them while accounting for the corresponding paths. For each node $v$, we store $2$ longest paths we have obtained so far (say of length $l_1(v)$ and $l_2(v)$, with $l_1 \geq l_2$), which end at that node. Initially set all these values to zero.

  1. Let $v$ a terminal vertex in the tree and let $(u,v)$ be the edge touching it.
  2. Set $l = l_1(v) + w(u,v)$.
  3. Modify $l_1(u)$ and $l_2(u)$ by picking the largest two among $l_1(u)$, $l_2(u)$ and $l$.
  4. Remove the terminal node $v$ and its edge $(u,v)$ from the tree. If the tree is not empty (no edges), go back to step $1$.

When all edges have been removed, we can show that maximum path length is given by $\max {(l_1(v) + l_2(v))}$, over all nodes $v$ in the original tree. Each vertex and edge is visited exactly once and all the operations are constant time, so the algorithm is linear in the number of vertices.

I assumed here that an empty path (path with no edges) is admissible and has length $0$ (for example, when all edge weights are negative, empty path is the longest). But if you only want non-empty paths, you could change the initialization of $l_1$ and $l_2$ values for all nodes to $-\infty$ instead of $0$.

$\endgroup$
0
$\begingroup$

I want to propose a different $\mathcal{O}(n)$ algorithm. We will pick any node $u$ and start dfs from it. Our $dfs$ will return two things.

  1. Longest simple path with $u$ as the end node of the simple path which we will call as $V_{1u}$
  2. Longest simple path in the subtree $u$ which we call as $V_{2u}$

Let $u$ have $i$ children. $u_1, u_2, \dots, u_i$. Our $dfs(u_j)\ \forall\ 1 \leq j \leq i$ will recursively calculate answer for $u_1, u_2, \dots, u_i$. For every child, we will get two values as mentioned before. Now, we will use these values to calculate the {answer pair} for node $u$ using the following way

  1. Longest simple path with $u$ as the end node($V_{1u}$) will be $max(w(u, u_j) + V_{1u_j}) \forall 1 \leq j \leq i$ which will be calculated in the $\mathcal{O}(i)$ time.
  2. Longest simple path in $u's$ subtree($V_{2u}$) will be the $max$ of the following things :- $max(V_{2u_j})$, $V_{1u}$, longest simple path with $u$ as one of it's nodes

To Calculate Longest simple path with $u$ as one of its nodes (i.e. Simple paths going between two of its childrens) will be simply $max(w(u, u_j) + V_{1u_j} + w(u, u_k) + V_{1u_k}) \forall 1 < j < k < i$. So, we have to essentially select maximum and second maximum from $w(u, u_j) + V_{1u_j}$ which we can do in linear time(with respect to the size of the children of $u$). Hence, we can return both the values in a total of $O(n)$ time.

$\endgroup$

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.