### todorokishotoua1's blog

By todorokishotoua1, history, 8 months ago, 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.

Dominating Set Definition  Comments (2)
 » 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]$ as follows:States: $dp[i]$ equals the minimum number of nodes in $S$ in the subtree of $i$ such that $i \in S$ and all nodes in the subtree of $i$ (not including $i$ itself) are valid according to the statement. $dp[i]$ equals the minimum number of nodes in $S$ in the subtree of $i$ such that $i \not \in S$ but $i$ has a child in $S$ and all nodes in the subtree of $i$ (not including $i$ itself) are valid according to the statement. $dp[i]$ equals the minimum number of nodes in $S$ in the subtree of $i$ such that $i \not \in S$ and $i$ doesn't have a child in $S$ and all nodes in the subtree of $i$ (not including $i$ itself) are valid according to the statement. 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): $dp[i] = 1$ (we can add $i$ to $S$; this is valid and $|S| = 1$) $dp[i] = 10^6$ (there is no way for $i$ to have a child in $S$ as $i$ has no children. Also note that any value $> n$ works here, not just $10^6$. Here I'm assuming that $n \le 2 \cdot 10^5$) $dp[i] = 0$ (we can choose to not add $i$ to $S$; this is valid (for now) and $|S| = 0$) If $|C_i| > 0$: $dp[i] = \displaystyle\sum_{j \in C_i}dp[j]$ (in order to have $i \in S$, no children of $i$ can be in $S$ and also no children of $i$ can have their children in $S$ so that the children of $i$ are not adjacent to multiple nodes in $S$) $dp[i] = \displaystyle\min_{k \in C_i}(dp[k]+\sum_{j \in C_i \setminus k}dp[j])$ (in order to have $i \not \in S$ but a child of $i$ in $S$, exactly one child of $i$ has to be in $S$. As $i \not \in S$, all other children of $i$ have to have a child in $S$ in order to be adjacent to some node in $S$) $dp[i] = \displaystyle\sum{j \in C_i}dp[j]$ (in order to have $i \not \in S$ and no child of $i$ in $S$, all children of $i$ have to have a child in $S$ in order to be adjacent to some node in $S$) After the dp has been calculated up to the root, we will have three dp values for the root. $dp$ is not a valid solution, as (by definition) $0 \not \in S$ and $0$ doesn't have any children in $S$. $dp$ and $dp$ are valid solutions and thus, the answer to the problem is $\min(dp, dp)$. 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]$ can be calculated in $O(|C_i|)$ by first calculating $\displaystyle\sum_{j \in C_i}dp[j]$ in $O(|C_i|)$ and then calculating the value for each $k \in C_i$ as $dp[k]+\left(\displaystyle\sum_{j \in C_i}dp[j]\right) - dp[k]$ 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!