Find k vertices in a tree forming maximum length path

Revision en1, by egor.okhterov, 2017-03-10 22:22:21

We have a tree with n (2 ≤ n ≤ 1000) nodes and we need to find k (1 ≤ k ≤ 100 and k ≤ n - 1) vertices such that the path going through all of these vertices has the maximum length.

Note:

  • The path should start at vertex 1 and finish also at vertex 1.
  • The algorithm has to return just the length of the maximum path (the path itself is not needed).
  • The weight for the edge has following restrictions: 0 ≤ w ≤ 100000.

Let's say we have the following tree with n = 5 vertices:

We need to find k = 3 vertices which will give us the longest path.

For this tree the maximal path is the following:
15241

It has the total length of 13 + 18 + 10 + 5 = 46.
So, for that particular tree we have to print 46 as our result.


I came up with a following greedy/dp-like solution. First we solve the problem for k = 1 and we remember this solution in a linked list 1v1. After that we try to solve the problem for k = 2 by trying all of the remaining n - 2 vertices and insert it in the current path: 1uv1 and 1vu1. After going through all of the vertices we choose the one which gave us the best result. Then we proceed to solve k = 3.

The problem is that it looks like this solution is not correct, because it fails the tests for this problem. I cannot prove that my solution is correct and I cannot disprove it. All I managed to do is to generate millions of different random trees and in all of these cases my clever solution matched bruteforce solution.

For now all my effort is directed towards generating a counter example in which my method will fail, but if it is correct I'd be glad to see the reasoning why is it correct.

Tags weighted tree, dynamic programming, all-shortest-path

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English egor.okhterov 2017-03-10 22:58:22 50
en3 English egor.okhterov 2017-03-10 22:53:35 16 Tiny change: 'tebin.com/rt9g70RH) is not c' -> 'tebin.com/kvhPSSUw) is not c'
en2 English egor.okhterov 2017-03-10 22:26:57 5 Tiny change: 'eight for the edge has ' -> 'eight for an edge has '
en1 English egor.okhterov 2017-03-10 22:22:21 2047 Initial revision (published)