Advanced

Spotting Trees with Few Leaves

Björklund, Andreas LU ; Kamat, Vikram; Kowalik, Lukasz and Zehavi, Meirav (2015) International Colloquium on Automata, Languages, and Programming In Lecture Notes in Computer Science/Automata, Languages, and Programming 9134. p.243-255
Abstract
We show two results related to the Hamiltonicity and k -Path algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) 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 iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few... (More)
We show two results related to the Hamiltonicity and k -Path algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) 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 iterated random bipartition employed by the algorithm 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 k-Path and Hamiltonicity in any graph of maximum degree Δ=4,…,12 or with vector chromatic number at most 8. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Lecture Notes in Computer Science/Automata, Languages, and Programming
editor
Haldorsson, Magnus. M.; Iwama, Kazou; Kobayashi, Naoki; Speckmann, Bettina; ; ; and
volume
9134
pages
243 - 255
publisher
Springer
conference name
International Colloquium on Automata, Languages, and Programming
external identifiers
  • wos:000364317700020
  • scopus:84950132799
ISSN
1611-3349
0302-9743
ISBN
978-3-662-47672-7
DOI
10.1007/978-3-662-47672-7_20
project
Exact algorithms
language
English
LU publication?
yes
id
d0e966b8-c9e3-4c0f-a007-6d3db95b72ec (old id 7516038)
date added to LUP
2015-07-20 10:17:38
date last changed
2017-09-12 13:06:58
@inproceedings{d0e966b8-c9e3-4c0f-a007-6d3db95b72ec,
  abstract     = {We show two results related to the Hamiltonicity and k -Path algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) 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 iterated random bipartition employed by the algorithm 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 k-Path and Hamiltonicity in any graph of maximum degree Δ=4,…,12 or with vector chromatic number at most 8.},
  author       = {Björklund, Andreas and Kamat, Vikram and Kowalik, Lukasz and Zehavi, Meirav},
  booktitle    = {Lecture Notes in Computer Science/Automata, Languages, and Programming},
  editor       = {Haldorsson, Magnus. M. and Iwama, Kazou and Kobayashi, Naoki and Speckmann, Bettina},
  isbn         = {978-3-662-47672-7},
  issn         = {1611-3349},
  language     = {eng},
  pages        = {243--255},
  publisher    = {Springer},
  title        = {Spotting Trees with Few Leaves},
  url          = {http://dx.doi.org/10.1007/978-3-662-47672-7_20},
  volume       = {9134},
  year         = {2015},
}