Finding all longest unique paths in tree

Question

Let us assume that we have a tree consisting on N nodes. The task is to find all longest unique paths in the tree. For example, if the tree looks like following:

Then there are three longest unique paths in the tree: 1 - 2 - 3 - 4 - 5, 6 - 2 - 3 - 4 - 5 and 1 - 2 - 6.

I want to programmatically find and store all such paths for a given tree. One way to do it would be to compute paths between each pair of node in the tree and then reject the paths which are contained in any other path. However, I am looking for an efficient way to do it. My questions are as follows:

• Is it possible to compute this information in less than O(N^2)? I have not been able to think of a solution which would be faster than O(N^2).
• If yes, could you be kind enough to guide me towards the solution.

The reason why I want to try it out is because I am trying to solve this problem: KNODES

Answer 1

An algorithm with a time complexity below O(N^2) may only exist, if every solution for a tree with N nodes can be encoded in less than O(N^2) space.

Suppose a complete binary tree with n leaves (N=n log n). The solution to the problem will contain a path for every set of 2 leaves. That means, the solution will have O(n^2) elements. So for this case we can encode the solution as the 2-element sets of leaves.

Now consider a nearly complete binary tree with m leaves, which was created by only removing arbitrary leaves from a complete binary tree with n leaves. When comparing the solution of this tree to that of the complete binary tree, both will share a possibly empty set of paths. In fact for every subset of paths of a solution of a complete binary tree, there will exist at least one binary tree with m leaves as mentioned above, that contains every solution of such a subset. (We intentionally ignore the fact that a tree with m leaves may have some more paths in the solution where at least some of the path ends are not leaves of the complete binary tree.)

Only that part of the solution for a binary tree with m leaves will be encoded by a number with (n^2)/2 bits. The index of a bit in this number represents an element in the upper right half of a matrix with n columns and rows.

For n=4 this would be:

x012
xx34
xxx5

The bit at index i will be set if the undirected path row(i),column(i) is contained in the solution.

As we have already statet that a solution for a tree with m leaves may contain any subset of the solution to the complete binary tree with n>=m leaves, every binary number with (n^2)/2 bits will represent a solution for a tree with m leaves.

Now encoding every possible number with (n^2)/2 bits with less than (n^2)/2 is not possible. So we have shown that solutions at least require O(n^2) space to be represented. Using N=n log n from above we yield a space requirement of at least O(N^2).

Therefore there doens't exist an algorithm with time complexity less than O(N^2)

Answer 2

As far as I could understand, you have a tree without a selected root. Your admissible paths are the paths that do not allow to visit tree nodes twice (you are not allowed to return back). And you need to find all such admissible paths that are not subpaths of any admissible path.

So if I understood right, then if a node has only one edge, than the admissible path either start or stop at this node. If tree is connected, then you can get from any node to any node by one admissible path.

So you select all nodes with one edge, call it S. Then select one of S and walk the whole tree saving the paths to the ends (path, not the walk order). Then you do this with every other item in S and remove duplicated paths (they can be in reverse order: like starting from 1: 1 - 2 - 6 and starting from 6: 6 - 2 - 1).

So here you have to visit all the nodes in the tree as much times as you have leafs in the tree. So complexity depends on the branching factor (in the worst case it is O(n^2). There are some optimizations that can reduce the amount of operations, like you don't have to walk the tree from the last of S.