2015/02/26 by Meirav Zehavi, Zehavi, Meirav · 2 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1502.07725
arxiv created 2015/05/11 · arxiv updated 2015/05/12
Given an undirected graph G and a parameter k, the k-Leaf Spanning Tree (k-LST) problem asks if G contains a spanning tree with at least k leaves. This problem has been extensively studied over the past three decades. In 2000, Fellows et al. [FSTTCS'00] explicitly asked whether it admits a klam value of 50. A steady progress towards an affirmative answer continued until 5 years ago, when an algorithm of klam value 37 was discovered. In this paper, we present an O^*(3.188k)-time parameterized algorithm for k-LST, which shows that the problem admits a klam value of 39. Our algorithm is based on an interesting application of the well-known bounded search trees technique, where the correctness of rules crucially depends on the history of previously applied rules in a non-standard manner.