<p>For  k edge-weighted trees $T_1,T_2...T_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum_{i=1}^k d_i(x,y)$$ where $d_i(x,y)$ denotes the sum of weights of the edges in the path between x and y in $T_i$.</p>

<p>Recently I came across the $k \leq 3$ version of this problem, which can be solved in $O(n\log(n))$. But for general k, is there any way to get a complexity lower than $O(n^2)$ (assuming k is a constant)?</p>

CC BY-SA 3.0
2018-02-26T10:18:01.700Z
Is there any relation between the trees other than that they contain the same nodes?
John Dvorak
CC BY-SA 3.0
2018-02-26T11:21:31.337Z
I assume there's nope. I forgot to mention n in the question :/ my fault.
newbie
CC BY-SA 3.0
2018-02-26T20:20:02.717Z
Is there a reference for the $k\leq 3$ algorithm?
Chao Xu
CC BY-SA 3.0
2018-02-27T00:04:50.670Z
@ChaoXu http://uoj.ac/problem/347 solution: https://drive.google.com/file/d/1J2vOg9UEHVpHquhMTkCu5iQh3bU0JZpO/view?usp=sharing (in chinese)
newbie
CC BY-SA 3.0
2018-02-28T12:29:17.370Z
Can we even do the special case when all trees are paths?
daniello
CC BY-SA 3.0
2018-02-28T14:24:07.013Z
@daniello When all trees are paths, for each tree calculate the distance of every point to one end of the path, then the problem can be regarded as finding the furthest pair of points where the distance is defined as k-dimensional manhattan distance. It can obviously be solved in time $O(2^kkn)$ (by enumerating the absolute value signs).
newbie
CC BY-SA 3.0
2018-02-28T21:00:35.923Z
Can you elaborate on your $2^kkn$ algorithm for furthest pair in k dimensional manhattan distance? If it is long enough make it an answer and mark it as a “partial answer”? At least I do not see it from your brief explanation and would be interested in knowing how it works.
daniello
CC BY-SA 3.0
2018-03-01T00:12:47.753Z
@daniello because |x|=max(x,-x), so for something like |x1-y1|+|x2-y2|+|x3-y3|, we can enumerate k1,k2,k3 in {-1,1}, and find the maximum of k1(x1-y1)+k2(x2-y2)+k3(x3-y3) (and take the max of these maximums). If sth has got the wrong sign, it will not affect general answer.
newbie
CC BY-SA 3.0
2018-03-01T09:19:39.940Z
What about the input set $u_1 = [-10, -10], u_2 = [-1, -11], u_3 = [-11, -1], v_1 = [10, 10], v_2 = [1, 11], v_3 = [11, 1]$? Here the furthest pair is $u_1$, $v_1$ but they are not the extremal points along any axis?
daniello
CC BY-SA 3.0
2018-03-01T10:20:36.233Z
@daniello in your example, take k1=k2=1, v1 is the point with maximum k1*x+k2*y, and u1 is the point with minimum. We're not taking extremal points along axis, but for every vector of length k consisted of {-1,1}, taking scalar products with these points and check the maximum and minimum.
newbie
<ds.algorithms><graph-algorithms><complexity-classes><tree><parameterized-complexity>
Find a pair of nodes with maximum sum of distances in k given trees
newbie
# Find a pair of nodes with maximum sum of distances in k given trees

(Asked by: username_0 on 2018-02-26)

For k edge-weighted trees $T\_1,T\_2...T\_k$ which contain the same set of nodes $\{1,2,... n \}$, I want to find a pair of nodes $(x,y)$ which maxifies $$\sum\_{i=1}^k d\_i(x,y)$$ where $d\_i(x,y)$ denotes the sum of weights of the edges in the path between x and y in $T\_i$.

Recently I came across the $k \leq 3$ version of this problem, which can be solved in $O(n\log(n))$. But for general k, is there any way to get a complexity lower than $O(n^2)$ (assuming k is a constant)?

**Tags:** ds.algorithms, graph-algorithms, complexity-classes, tree, parameterized-complexity
> **Comments:**
> **username_1**: Is there any relation between the trees other than that they contain the same nodes?  
> **username_0**: I assume there's nope. I forgot to mention n in the question :/ my fault.  
> **username_2**: Is there a reference for the $k\leq 3$ algorithm?  
> **username_0**: @ChaoXu http://uoj.ac/problem/347 solution: https://drive.google.com/file/d/1J2vOg9UEHVpHquhMTkCu5iQh3bU0JZpO/view?usp=sharing (in chinese)  
> **username_3**: Can we even do the special case when all trees are paths?  
> **username_0**: @daniello When all trees are paths, for each tree calculate the distance of every point to one end of the path, then the problem can be regarded as finding the furthest pair of points where the distance is defined as k-dimensional manhattan distance. It can obviously be solved in time $O(2^kkn)$ (by enumerating the absolute value signs).  
> **username_3**: Can you elaborate on your $2^kkn$ algorithm for furthest pair in k dimensional manhattan distance? If it is long enough make it an answer and mark it as a “partial answer”? At least I do not see it from your brief explanation and would be interested in knowing how it works.  
> **username_0**: @daniello because |x|=max(x,-x), so for something like |x1-y1|+|x2-y2|+|x3-y3|, we can enumerate k1,k2,k3 in {-1,1}, and find the maximum of k1(x1-y1)+k2(x2-y2)+k3(x3-y3) (and take the max of these maximums). If sth has got the wrong sign, it will not affect general answer.  
> **username_3**: What about the input set $u_1 = [-10, -10], u_2 = [-1, -11], u_3 = [-11, -1], v_1 = [10, 10], v_2 = [1, 11], v_3 = [11, 1]$? Here the furthest pair is $u_1$, $v_1$ but they are not the extremal points along any axis?  
> **username_0**: @daniello in your example, take k1=k2=1, v1 is the point with maximum k1*x+k2*y, and u1 is the point with minimum. We're not taking extremal points along axis, but for every vector of length k consisted of {-1,1}, taking scalar products with these points and check the maximum and minimum.  

---

## 0 answers

