2015/01/03 by Andreas Björklund, Björklund, Andreas, Vikram Kamat +5
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1501.00563
arxiv created 2015/02/22 · arxiv updated 2015/02/24
We show two results related to the Hamiltonicity and k-Path algorithms in undirected graphs by Björklund [FOCS'10], and Björklund et al., [arXiv'10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O^*(1.657k2l/2) time. It can be applied as a subroutine to solve the k-Internal Spanning Tree (k-IST) 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 iterated random bipartition employed by the algorithm 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 k-Path and Hamiltonicity in any graph of maximum degree Δ=4,…,12 or with vector chromatic number at most 8.