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.
Read More: http://epubs.siam.org/doi/abs/10.1137/15M1048975 (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/92caa3e9-ac78-42b5-b0ed-57a78a246423
- 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
- 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}}, }