Spotting Trees with Few Leaves
(2017) In SIAM Journal on Discrete Mathematics 31(2). p.687713 Abstract
 We show two results related to finding trees and paths in graphs. First, we show that in $O^*(1.657^k2^{l/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.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 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... (More)
 We show two results related to finding trees and paths in graphs. First, we show that in $O^*(1.657^k2^{l/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.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 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 $\Delta=4,\ldots,12$ or with vector chromatic number at most 8. Our results extend the technique by Björklund [SIAM J. Comput., 43 (2014), pp. 280299] 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.
Read More: http://epubs.siam.org/doi/abs/10.1137/15M1048975 (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/92caa3e9ac7842b5b0ed57a78a246423
 author
 Björklund, Andreas ^{LU} ; Kamat, Vikram; Kowalik, Lukasz and Zehavi, Meirav
 organization
 publishing date
 2017
 type
 Contribution to journal
 publication status
 published
 subject
 in
 SIAM Journal on Discrete Mathematics
 volume
 31
 issue
 2
 pages
 27 pages
 publisher
 SIAM Publications
 external identifiers

 scopus:85021899725
 wos:000404770300003
 ISSN
 08954801
 DOI
 10.1137/15M1048975
 language
 English
 LU publication?
 yes
 id
 92caa3e9ac7842b5b0ed57a78a246423
 date added to LUP
 20170414 12:23:26
 date last changed
 20170918 13:32:29
@article{92caa3e9ac7842b5b0ed57a78a246423, abstract = {We show two results related to finding trees and paths in graphs. First, we show that in $O^*(1.657^k2^{l/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.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 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 $\Delta=4,\ldots,12$ or with vector chromatic number at most 8. Our results extend the technique by Björklund [SIAM J. Comput., 43 (2014), pp. 280299] 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.<br/><br/><br/>Read More: http://epubs.siam.org/doi/abs/10.1137/15M1048975}, author = {Björklund, Andreas and Kamat, Vikram and Kowalik, Lukasz and Zehavi, Meirav}, issn = {08954801}, language = {eng}, number = {2}, pages = {687713}, publisher = {SIAM Publications}, series = {SIAM Journal on Discrete Mathematics}, title = {Spotting Trees with Few Leaves}, url = {http://dx.doi.org/10.1137/15M1048975}, volume = {31}, year = {2017}, }