1
$\begingroup$

I'm given a (not necessarily binary) tree. Now every node can have a signal with range $i$, reaching all nodes being at most $i$ edges away. The cost of a signal is determined by a function $f(n, i)$ with $n$ being a node and $i$ being the signal strenght. The cost for each node may vary, the only assumption one can make is that $f(n, i) \geq f(n, j)$ for $i > j$.

I need to find the minimum cost to cover the whole tree.

Example:

tree

For $f(n, i) = (i + 1)^2$, the minimum cost would be 7:

Setting a signal with strenght 0 for every node covers the whole tree for the cost of 7. Setting a signal with strenght 1 for the nodes $b$ and $c$ covers the tree for the cost of 8 and setting a signal with strenght 2 for node $a$ results in a cost of 9.

Using Dynamic Programmming this task should be achieved in $O(n^2)$. This is an assignment so I'd be grateful for tips.

$\endgroup$
  • $\begingroup$ Is it the tree rooted/directed? (The signal only reach children but no parents) As nothing is stated regarding this I'm assuming it isn't, but the arrows in the picture suggest this. $\endgroup$ – Marcelo Fornet Jun 15 at 15:04
  • $\begingroup$ Already answered my question with this line: Setting a signal with strenght 1 for the nodes b and c covers the tree for the cost of 8 $\endgroup$ – Marcelo Fornet Jun 15 at 15:06
  • $\begingroup$ Hint: for $i \ge 0$ and a vertex $v$, define $OPT_{down}[v,i]$ as the minimum cost needed to cover the subtree rooted at $v$ if all the nodes at distance $<i$ from $v$ are always considered as covered. Define $OPT_{up}[v,i]$ as the minimum cost needed to cover the subtree $T_v$ rooted at $v$ with the constraint that the selected signal strenghts should also be a fesible solution for the tree obtained by appending $T_v$ at the end of a path of $i$ vertices. $\endgroup$ – Steven Jun 15 at 15:07
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Jun 15 at 20:10
  • $\begingroup$ @Steven Could you elaborate on $OPT_{up}$? I don't understand what you mean by "appending $T_v$ at the end of a path of i vertices". Thank you for your tip $\endgroup$ – rn42v1r Jun 18 at 12:39
1
$\begingroup$

Let $T$ be your tree, and root it in an arbitrary vertex $r$. Given a vertex $v$, let $T_v$ denote the subtree of $T$ rooted at $v$. For simplicity, let $f(0, v) = 0$.

For $i \ge 0$, define $D[v,i]$ as the minimum cost needed to cover the subtree rooted at $v$ if all the nodes at distance smaller than $i$ from $v$ are always considered as covered. Intuitively this means that the signal "coming into $T_v$" is strong enough to cover all vertices of $ T_v$ at distance at most $i-1$ from $v$.

For $i \ge 0$, define $U[v,i]$ as the minimum cost needed to cover the subtree $T_v$ rooted at $v$ with the constraint that the selected signal strengths should also be a feasible solution for the tree obtained by appending a path of $i$ vertices to $v$. Intuitively this means that the signal "outgoing from $T_v$" is strong enough to cover all vertices of $T \setminus T_v$ at distance at most $i$ from $v$.

Notice that, by definition, $D[v,i] = U[v,i]$.

If $v$ is a leaf of $T$, then $$ D[v, i] = \begin{cases} f(v, 0) & \mbox{if } i=0 \\ 0 & \mbox{if } i>0 \\ \end{cases}, $$ and $$ U[v, i] = f(v, i). $$

If $v$ is not a leaf of $T$, then let $C_v$ be the set of children of $v$. For $i=0, \dots, n-1$:

$$ U[v, i] = \min \begin{cases} U[v, i+1] & \mbox{only if $i \neq n-1$}\\ f(v,i) + \sum_{u \in C_v} D[u, i] \\ \min_{z \in C_v} \left\{ U[z, i+1] + \sum_{u \in C_v \setminus {z}} D[u, i] \right\} & \mbox{only if $i \neq n-1$} \end{cases}, $$

and, for $i=1,\dots,n$:

$$ D[v, i] = \min \begin{cases} D[v, i-1] \\ \sum_{u \in C_v} D[u, i-1] \end{cases} $$

You can then compute all values $U[v, i]$ and $D[v,i]$ where $v$s are considered in postoder w.r.t. $T$ and the order of subproblems for a fixed vertex $v$ is $U[v,n-1], \dots, U[v,1], U[v,0] = D[v,0], D[v,1], \dots, D[v,n]$.

As far as the computational complexity is concerned notice that there are $O(n^2)$ subproblems. The overall time needed to evaluate the second argument of the minimum of $U[v,i]$ and $D[v,i]$ is $O(n^2)$ since, for each value of $i$, computing $\sum_{u \in C_v} D[u, i]$ takes time proportional to $|C_v|$ and $\sum_v |C_v| = O(n)$.

Suppose then that all the values $\sum_{u \in C_v} D[u, i]$ are known for free (since the time needed to compute them has already been accounted for). The overall time needed to evaluate the third argument of the minimum of $U[v,i]$ is again $O(n^2)$ since, for each value of $i$, $\sum_{u \in C_v \setminus {z}} D[u, i]$ can be found in time $O(1)$ by difference, and the inner minimum ranges over $|C_v|$ elements. Once again $\sum_v |C_v| = O(n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $\min_{z \in C_v} \left\{ U[z, i+1] + \sum_{u \in C_v \setminus {z}} D[u, i] \right\}$ also can't work if $i = n - 1$ just like $U[v, i+1]$, right? $\endgroup$ – rn42v1r Jun 19 at 10:17
  • $\begingroup$ With $U$ and $D$ calculated, how do I get the solution? $\endgroup$ – rn42v1r Jun 19 at 12:10
  • $\begingroup$ The solution is $U[r,0]$ by definition. $\endgroup$ – Steven Jun 19 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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