Faster fixed-parameter tractable algorithms for matching and packing problems

M. R. Fellows, C. Knauer, N. Nishimura, P. Ragde, F. Rosamond, U. Stege, D. M. Thilikos, S. Whitesides

Research output: Contribution to journalArticlepeer-review


We obtain faster algorithms for problems such as r-dimensional matching and r-set packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). This technique lets us combine Alon, Yuster and Zwick's color-coding technique with dynamic programming to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2 O(k)), an improvement over previous algorithms for some of these problems running in time O(n+k O(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.

Original languageEnglish (US)
Pages (from-to)167-176
Number of pages10
JournalAlgorithmica (New York)
Issue number2
StatePublished - Oct 2008


  • Color coding
  • Fixed parameter tractable
  • Graph matching
  • Parameterized complexity
  • Set packing

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Faster fixed-parameter tractable algorithms for matching and packing problems'. Together they form a unique fingerprint.

Cite this