Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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"? $\endgroup$– JuhoCommented Dec 2, 2018 at 19:53
-
1$\begingroup$ What did you try and where did you get stuck? $\endgroup$– JuhoCommented Dec 2, 2018 at 19:53
-
$\begingroup$ 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 $\endgroup$– user95614Commented Dec 2, 2018 at 20:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Any negative answer that says that no greedy algorithm will work cannot be proved rigorously since we do not have a definition of an greedy algorithm. So I will just say, no, it is very unlikely that there is a greedy algorithm that will always yield a minimum dominating set if it is given a tree graph as input.
The most common greedy algorithm for dominating set is to repeatedly selecting a vertex with the maximum number of adjacent vertices that are not selected and that are not connected to any vertices selected (not dominated) so far until all vertices are dominated. The following graph illustrates how soon it fails. In the first step we will select vertex 0, the only vertex whose degree is greater than 2. Then we will select vertex 2, 4, 6 for our dominating set. However, the minimal dominating set, {vertex 1, vertex 3, vertex 5} has only three vertices.
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.
A proper strategy to find a minimal dominating set for a tree is dynamic programming. Root the tree at an arbitrary vertex if it is not rooted yet. Now you start computing recursively the minimal dominating set for each subtree with its root included in the set as well as with its root not included in the set.
