1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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$.
$\endgroup$
1
  • $\begingroup$ Thank you. If we use dynamic programming approach, can we solve it in $O(nk)$? Could you give some hint about this $\endgroup$
    – ErroR
    Commented Apr 29, 2022 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.