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 , 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. Both problems may be solved, on -vertex graphs, in time . The maximum leaf problem is fixed-parameter tractable, meaning that it can be solved in time exponential in the number of leaves but only polynomial in the input graph size. The klam value of these algorithms (intuitively, a number of leaves up to which the problem can be solved within a reasonable amount of time) has gradually increased, as algorithms for the problem have improved, to approximately 37, and it has been suggested that at least 50 should be achievable. In graphs of maximum degree three, the connected dominating set and its complementary maximum leaf spanning tree problem can be solved in polynomial time, by transforming them into an instance of the matroid parity problem for linear matroids. Applications Connected dominating sets are useful in the computation of routing for mobile ad hoc networks. In this application, a small connected dominating set is used as a backbone for communications, and nodes that are not in this set communicate by passing messages through neighbors that are in the set. The max leaf number has been employed in the development of fixed-parameter tractable algorithms: several NP-hard optimization problems may be solved in polynomial time for graphs of bounded max leaf number. See also Universal vertex, a vertex that (when it exists) gives a minimum connected dominating set of size one References Computational problems in graph theory Graph connectivity