SPOTTING TREES WITH FEW LEAVES.

We show two results related to finding trees and paths in graphs. First, we show that in O*(1.657k21/2) time one can either find a k-vertex tree with l leaves in an n-vertex undirected graph or conclude that such a tree does not exist. Our solution can be applied as a subroutine to solve the k-INTERNAL SPANNING Tree problem in O* (min(3.455k, 1.946n)) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of O*(2n). Second, we show that the running time can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for HAMILTONICITY and k-PATH in any graph of maximum degree Δ = 4,..., 12 or with vector chromatic number at most 8. Our results extend the technique by Björklund [SIAM J. Comput., 43 (2014), pp. 280-299] and Björklund et al. [Narrow Sieves for Parameterized Paths and Packings, CoRR, arXiv:1007. 1161, 2010] to finding structures more general than paths as well as refine it to handle special classes of graphs more efficiently.r [ABSTRACT FROM AUTHOR]