Find a path with given weight and the minimum number of edges on a tree

Question

Suppose given a positively-weighted tree $T=(V,E,w)$ and $k\in \mathbb{N}$, where $|V|=n$, the weight function $w:E\to\mathbb{N}$, and each node has degree at most $3$. How we can find a path on $T$ that has weight $k$ and the minimum number of edges in $O(n\log^2n)$?

I think we can use BFS because BFS give us the shortest path in term of number of edges.

Answer 1

This answer explains an algorithm that finds the minimum number of edges in $O(n\log n)$ time. With more bookkeeping, the path of weight $k$ with that minimum number of edges can also be found in $O(n\log n)$ time.

A Basic Idea: Numbers with Offset

If $S$ is a set of numbers and $d$ is a number, let $\mathcal N(S,d):=\{s+d\mid s\in S\}$. This notation/data structure is handy.

1. If the numbers in $S$ can be accessed directly, so are numbers in $N(S, d)$.
2. To denote $\{s + d' | s\in \mathcal N(S,d)\}$, we can use $\mathcal N(S, d+d')$.
3. It takes $O(\min(\#(S_1), \#(S_2))$ time to compute $S$ and $d$ such that $\mathcal N(S, d)= \mathcal N(S_1, d_1) \cup \mathcal N(S_2, d_2)$.

The data structure in the next section is an extension of this notation.

Map with Offsets (MO)

A MO $\mathcal M$ is a map from weights to lengths together with a weight offset $\mathcal M_{\text w}$ and a length offset $\mathcal M_{\text l}$. An entry in $\mathcal M$ (as a map), i.e., a key-value pair $(w,l)$ represent the knowledge that the minimum number of edges in a path of weight $w + \mathcal M_{\text w}$ is $l+\mathcal M_\text{l}$.

A MO with $s$ entries and another MO with $t$ entries can be merged into a MO with no more than $s+t$ entries, which shall represent the combined knowledge represented by the two former MOs, in $O(\min(s,t))$ time.

A Depth-First Search Method $\text{compute_min_edges}$

Input: a binary tree rooted at $r$ with weight function $w$ and a global variable $min\_len$.
Output: a MO that describes the paths starting from $r$.
Side effect: $min\_len$ updated.
Procedure:

• If $r$ has no children, return $(0, 0, \{0\to0\})$.

• Otherwise, a path that passes $r$ either starts from $r$, connecting to a node in one of two subtrees, or has one endpoint in each of two subtrees, or consists of $r$ only.

  1. for each child $c$ of $r$,
     1. call this method with the subtree rooted at $c$, which returns MO $M_c$.
     2. Add $w(r,c)$ to ${(M_c)}_\text{w}$. Add 1 to ${(M_c)}_\text l$.
     3. If $\mathcal M$ maps weight $k-{(M_c)}_\text w$ to some length smaller than $min\_len-{(M_c)}_\text l$, reduce $min\_len$ to that length plus ${(M_c)}_\text l$.
  2. If there is only one child, let $M_r$ be the only $M_c$ obtained. Otherwise, there are two children $c1$ and $c2$:
     1. Find all pairs $((u_{\text{w}}, u_{\text{l}}), (v_{\text{w}}, v_{\text{l}}))$ such that $(u_{\text{w}}, u_{\text{l}})$ is an entry in $M_{c1}$, $(v_{\text{w}}, v_{\text{l}})$ is an entry $M_{c2}$, and $$u_{\text{w}} + {(M_{c1})}_\text w+v_{\text{w}} + {(M_{c2})}_\text w=k.$$ For each pair, if $u_{\text{l}} + {(M_{c1})}_\text l+v_{\text{l}} + {(M_{c2})}_\text l<min\_len$, reduce $min\_len$ to the former.
        This step can be done in $O(\min(\#M_{c1},\#M_{c1}))$ time, where $\#\mathcal M$ is the number of entries in MO $\mathcal M$.
     2. Merge $M_{c1}$ and $M_{c2}$ into $M_r$.

  Let $M_r$ map ${-}(M_r)_{\text w}$ to ${-}(M_r)_{\text l}$.
  Return $M_r$.

The Algorithm in $O(n\log n)$ Time

1. Initialize a global variable $min\_len=\infty$.
2. Call $\text{compute_min_edges}$ with the given weighted tree, after picking an arbitrary node as the root.
3. Return $min\_len$, which is the minimum number of edges in a path that has weight $k$.