Algorithms
It is NP-complete to test whether there exists a connected dominating set with size less than a given threshold, or equivalently to test whether there exists a spanning tree with at least a given number of leaves. Therefore, it is believed that the minimum connected dominating set problem and the maximum leaf spanning tree problem cannot be solved in polynomial time.
When viewed in terms of approximation algorithms, connected domination and maximum leaf spanning trees are not the same: approximating one to within a given approximation ratio is not the same as approximating the other to the same ratio. There exists an approximation for the minimum connected dominating set that achieves a factor of 2 ln Δ + O(1), where Δ is the maximum degree of a vertex in G. The maximum leaf spanning tree problem is MAX-SNP hard, implying that no polynomial time approximation scheme is likely. However, it can be approximated to within a factor of 2 in polynomial time.
Read more about this topic: Connected Dominating Set