Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

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
; ; and
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
Society for Industrial and Applied Mathematics
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
2022-04-01 08:13:34
@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    = {{Society for Industrial and Applied Mathematics}},
  series       = {{SIAM Journal on Discrete Mathematics}},
  title        = {{Spotting Trees with Few Leaves}},
  url          = {{http://dx.doi.org/10.1137/15M1048975}},
  doi          = {{10.1137/15M1048975}},
  volume       = {{31}},
  year         = {{2017}},
}