So I came accross the following problem :

**Given a rooted tree, find a minimum dominating set such that no two vertices in the dominating set share an edge and for all the vertices that is not in the set, there exists exactly one vertex in the set which is its neighbor. If such a set does not exists, report -1.**

I know there is a dp solution for finding the minimum dominating set of a given tree, but i have no idea as to how to approach this question, especially since my dp on trees is really weak.

Any help as to how to approach the problem will be really appreciated. Thank you.

I guess the solution would look something like this:

Let $$$n$$$ be the number of nodes, let $$$i = 0$$$ be the root node and let $$$C_i$$$ be the set of all direct children of $$$i$$$ for any node $$$i$$$. We will define a dp array $$$dp[n][3]$$$ as follows:

States:

For all $$$dp[i][j]$$$ if there exists no solution, we will have $$$dp[i][j] > n$$$ to denote that no solution exists. This works because for a valid solution, the number of nodes in $$$S$$$ can never exceed $$$n$$$. This is done in order to make implementation easier.

Transitions:

If $$$|C_i| = 0$$$ ($$$i$$$ has no children):

If $$$|C_i| > 0$$$:

After the dp has been calculated up to the root, we will have three dp values for the root. $$$dp[0][2]$$$ is not a valid solution, as (by definition) $$$0 \not \in S$$$ and $$$0$$$ doesn't have any children in $$$S$$$. $$$dp[0][0]$$$ and $$$dp[0][1]$$$ are valid solutions and thus, the answer to the problem is $$$\min(dp[0][0], dp[0][1])$$$. If this answer is $$$> n$$$, no solution exists.

All transitions can be calculated in $$$O(|C_i|)$$$ and thus, the total complexity is $$$O(\sum |C_i|) = O(n)$$$. (The transition for $$$dp[i][1]$$$ can be calculated in $$$O(|C_i|)$$$ by first calculating $$$\displaystyle\sum_{j \in C_i}dp[j][1]$$$ in $$$O(|C_i|)$$$ and then calculating the value for each $$$k \in C_i$$$ as $$$dp[k][0]+\left(\displaystyle\sum_{j \in C_i}dp[j][1]\right) - dp[k][1]$$$ in $$$O(|C_i|)$$$ and then taking the minimum.)

Please let me know if you think there is something wrong with my approach or if I've made a mistake somewhere.

This looks really good to me. Since at every step dp transition is only dealing with children of i, I will try to prove the dp recurrence by using induction on the height of the tree.

Thank you for this amazing solution!