Advanced

Narrow sieves for parameterized paths and packings

Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko (2017) In Journal of Computer and System Sciences 87. p.119-139
Abstract

We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(d-1)n/2. Our techniques generalize an algebraic approach studied in various recent works.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Determinant, Edge coloring, Graph algorithm, k-Path, Multidimensional matching, Polynomial identity testing, Randomized algorithm, Set packing, Sieve
in
Journal of Computer and System Sciences
volume
87
pages
119 - 139
publisher
Elsevier
external identifiers
  • scopus:85015917603
  • wos:000400199000006
ISSN
0022-0000
DOI
10.1016/j.jcss.2017.03.003
language
English
LU publication?
yes
id
a7926a8a-cf52-4d7d-a293-1a65282a302e
date added to LUP
2017-04-10 12:33:47
date last changed
2018-04-29 04:37:44
@article{a7926a8a-cf52-4d7d-a293-1a65282a302e,
  abstract     = {<p>We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(d-1)n/2. Our techniques generalize an algebraic approach studied in various recent works.</p>},
  author       = {Björklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  issn         = {0022-0000},
  keyword      = {Determinant,Edge coloring,Graph algorithm,k-Path,Multidimensional matching,Polynomial identity testing,Randomized algorithm,Set packing,Sieve},
  language     = {eng},
  pages        = {119--139},
  publisher    = {Elsevier},
  series       = {Journal of Computer and System Sciences},
  title        = {Narrow sieves for parameterized paths and packings},
  url          = {http://dx.doi.org/10.1016/j.jcss.2017.03.003},
  volume       = {87},
  year         = {2017},
}