# Greedy algorithm to find Minimum Dominating Set in a tree

Is it possible to find minimum dominating set on a tree $$G$$ using a greedy algorithm?

• What greedy algorithm do you have in mind? Also, do you mean "is it sometimes possible" or "does it always find a minimum dom. set"? – Juho Dec 2 '18 at 19:53
• What did you try and where did you get stuck? – Juho Dec 2 '18 at 19:53
• This is what I have (It's obviously not a complete solution): Given a tree T that arbitrarily roots T, choose an arbitrary leaf v with parent u, add u to the DS, delete u and all its children. The algorithm repeats as long as the resulting forest is nonempty. @Juho – encrypt0r Dec 2 '18 at 20:02

Furthermore, any strategy that avoids selecting a vertex that has been dominated might not succeed at all. According to Do Almost All Trees Have No Perfect Dominating Set? by BQ Yue, the average number of perfect dominating sets among all trees of order $$n$$ is likely approaching zero as $$n$$ goes to infinity.