Find a simple path in given tree with minimum number of edges

220 Views Asked by At

Suppose given a Tree $T=(V,E)$. Each nodes in $T$ has a degree at most two. Also, edges in $T$ has weight distinct and positive natural. Suppose $|V|=n$, our goal is find a simple path with length given input number $k$ and has minimum number of edges. Also we try find a divide and conquer approach that has running time $O(n\log^2 n)$.

I think we must find a $v\in V$ such that $v$ subtrees have at most $\frac{n}{2}$ nodes. Then we divide $v$ into subtrees and then we solve our problem recursively .

1

There are 1 best solutions below

0
On

The fact that each vertex has degree at most 2 tells you exactly what this tree looks like. Try drawing it, then use that structure to decide on a good way to divide your graph into subtrees with $\frac{n}{2}$ nodes.

By the way, the question asks specifically for divide-and-conquer, but again, the very simple structure of this graph means you can solve this in linear time. There are only at most two minimal simple paths of cost $\ge k$ which start at each node, one which "starts" there and one which "ends" there. You can iterate along your graph, starting at a "leaf" node and constructing the minimal $\ge k$ path from there, then moving to the next node (i.e. deleting the first edge) and adding as many edges to the "end" as you need to, and repeating for each node. You only check if the current path is long enough once for each time you add or remove an edge, and you only add and remove each edge once, so it only takes $2n$ comparisons and $2n$ additions or subtractions.