Narrow sieves for parameterized paths and packings
(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:
https://lup.lub.lu.se/record/a7926a8a-cf52-4d7d-a293-1a65282a302e
- author
- Björklund, Andreas LU ; Husfeldt, Thore LU ; Kaski, Petteri and Koivisto, Mikko
- organization
- publishing date
- 2017-08
- 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
- project
- Algebraic Graph Algorithms
- Exact algorithms
- language
- English
- LU publication?
- yes
- id
- a7926a8a-cf52-4d7d-a293-1a65282a302e
- date added to LUP
- 2017-04-10 12:33:47
- date last changed
- 2025-02-04 16:14:49
@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}}, keywords = {{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}}, doi = {{10.1016/j.jcss.2017.03.003}}, volume = {{87}}, year = {{2017}}, }