Parameter­ized Algorithms using Matroids

Matroids generalize linear independence, and they make a surprisingly useful data structure for parameterized algorithms. Starting from the basics, I build up to representative sets: small subfamilies with the guarantee that whenever some set in the original family can be completed to a solution, some set in the subfamily can be completed in the same way. Pruning a dynamic programming table down to such a subfamily keeps it small without losing the answer. I apply this to packing and matching problems (including faster deterministic algorithms for r-Dimensional Matching), and show how matroids also help in designing kernels.