Advanced

Spotting Trees with Few Leaves

Björklund, Andreas LU ; Kamat, Vikram; Kowalik, Lukasz and Zehavi, Meirav (2017) In SIAM Journal on Discrete Mathematics 31(2). p.687-713
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. 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.


Read More: http://epubs.siam.org/doi/abs/10.1137/15M1048975 (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
0895-4801
DOI
10.1137/15M1048975
language
English
LU publication?
yes
id
92caa3e9-ac78-42b5-b0ed-57a78a246423
date added to LUP
2017-04-14 12:23:26
date last changed
2017-09-18 13:32:29
@article{92caa3e9-ac78-42b5-b0ed-57a78a246423,
  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. 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.<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         = {0895-4801},
  language     = {eng},
  number       = {2},
  pages        = {687--713},
  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},
}