Narrow sieves for parameterized paths and packings

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

45 Citations (Scopus)
8 Downloads (Pure)

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.

Original languageEnglish
Pages (from-to)119–139
JournalJOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume87
DOIs
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • Determinant
  • Edge coloring
  • Graph algorithm
  • k-Path
  • Multidimensional matching
  • Polynomial identity testing
  • Randomized algorithm
  • Set packing
  • Sieve

Fingerprint

Dive into the research topics of 'Narrow sieves for parameterized paths and packings'. Together they form a unique fingerprint.

Cite this