Faster fixed-parameter tractable algorithms for matching and packing problems

We obtain faster algorithms for problems such as r-dimensional matching, r-set packing, graph packing, and graph edge 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). Previously such a kernel was known only for triangle packing. This technique lets us combine, in a new and sophisticated way, Alon, Yuster and Zwick's color-coding technique with dynamic programming on the structure of the kernel 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.