  Finding maximum-cardinality matchings in undirected graphs is arguably one of
the most central graph primitives. For $m$-edge and $n$-vertex graphs, it is
well-known to be solvable in $O(m\sqrt{n})$ time; however, for several
applications this running time is still too slow. We investigate how
linear-time (and almost linear-time) data reduction (used as preprocessing) can
alleviate the situation. More specifically, we focus on (almost) linear-time
kernelization. We start a deeper and systematic study both for general graphs
and for bipartite graphs. Our data reduction algorithms easily comply (in form
of preprocessing) with every solution strategy (exact, approximate, heuristic),
thus making them attractive in various settings.
