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 Δ