Minimum dominating set on trees

Question

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?

Answer 1

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