Faster fixed-parameter tractable algorithms for matching and packing problems

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.