# Minimum dominating set on trees

I am working on an NP-Complete problem, i.e., the dominating set. Given a graph $$G = (V, E)$$, a set $$S$$ is a dominating set if every vertex $$v \in V \setminus S$$ has at least one neighbor in $$S$$. I am looking for the complexity of the problem in trees. I have tried the greedy method to solve this problem. But, looks like a greedy algorithm would not work on trees. Is the problem polynomial time solvable? If yes, could someone point me to any references to this result?

The problem is solvable in linear time by dynamic programming.

Root a the input tree $$T$$ in an arbitrary vertex and let $$T_v$$ be the subtree of $$T$$ rooted in v.

Let $$OPT[v]$$ denote the size of a minimum dominating set of $$T_v$$. Let $$OPT^-[v]$$ denote the minimum size of a subset of vertices of $$T_v$$ that dominates all vertices in $$T_v$$ except, possibly, for $$v$$. Finally, let $$OPT^+[v]$$, denote the size of a minimum dominating set of $$T_v$$ that necessarily includes $$v$$.

If $$v$$ is a leaf then $$OPT[v]= OPT^+[v] = 1$$ and $$OPT^-[v] = 0$$.

Otherwise let $$u_1, \dots, u_k$$ be the children of $$v$$ in $$T$$. $$OPT^+[v] = 1 +\sum_{i=1}^k OPT^-[u_i]$$

$$OPT^-[v] = \min\{OPT^+[v], \sum_{i=1}^k OPT[u_i] \}$$

$$OPT[v] = \min \begin{cases} OPT^+[v]; \\ \min_{j=1,\dots,k} \left( OPT^+[u_j] + \sum_{\substack{i=1,\dots,k \\ i \neq j} } OPT[u_i] \right). \end{cases}$$

Notice that the above formulas for $$v$$ can be evaluated in time $$O(k)$$. The only one for which this might not be obvious is the second argument of the minimum in $$OPT[v]$$. This can be handled by first computing $$S = \sum_{i=1}^k OPT[u_i]$$ (in $$O(k)$$ time) and then noticing that, for a $$j=1,\dots, k$$, the desired quantity can be found in constant time as $$S - OPT[u_j] + OPT^+[u_j]$$.