Spotting Trees with Few Leaves

Summary, in English

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.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) problem in O∗(min(3.455^k,1.946^n)) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time, we break the natural barrier of O∗(2^n). 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.

• Author: Andreas Björklund; Vikram Kamat; Lukasz Kowalik; Meirav Zehavi
• Editor: Magnus. M. Haldorsson; Kazou Iwama; Naoki Kobayashi; Bettina Speckmann
• Department/s: Department of Computer Science; Parallel Systems
• Publishing year: 2015
• Language: English
• Pages: 243-255
• Publication/Series: Lecture Notes in Computer Science/Automata, Languages, and Programming
• Volume: 9134
• Links: http://dx.doi.org/10.1007/978-3-662-47672-7_20
• Document type: Conference paper
• Publisher: Springer
• Topic: Computer Science
• Conference name: International Colloquium on Automata, Languages, and Programming
• Conference date: 2015-07-08
• Status: Published
• Project: Exact algorithms
• Research group: Algorithms
• ISBN/ISSN/Other: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-662-47672-7