# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### Spotting Trees with Few Leaves

(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.

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
2017-04-14 12:23:26
date last changed
2019-04-10 03:41:19
```@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},
}

```