# Minimum cost of “signal” cover in a tree with DP

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:

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.

• 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. – Marcelo Fornet Jun 15 '20 at 15:04
• 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  – Marcelo Fornet Jun 15 '20 at 15:06
• 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. – Steven Jun 15 '20 at 15:07
• cs.stackexchange.com/tags/dynamic-programming/info – D.W. Jun 15 '20 at 20:10
• @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 – rn42v1r Jun 18 '20 at 12:39

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)$$.

• $\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? – rn42v1r Jun 19 '20 at 10:17
• With $U$ and $D$ calculated, how do I get the solution? – rn42v1r Jun 19 '20 at 12:10
• The solution is $U[r,0]$ by definition. – Steven Jun 19 '20 at 12:30