  In the fundamental Maximum Matching problem the task is to find a maximum
cardinality set of pairwise disjoint edges in a given undirected graph. The
fastest algorithm for this problem, due to Micali and Vazirani, runs in time
$\mathcal{O}(\sqrt{n}m)$ and stands unbeaten since 1980. It is complemented by
faster, often linear-time, algorithms for various special graph classes.
Moreover, there are fast parameterized algorithms, e.g., time
$\mathcal{O}(km\log n)$ relative to tree-width $k$, which outperform
$\mathcal{O}(\sqrt{n}m)$ when the parameter is sufficiently small.
  We show that the Micali-Vazirani algorithm, and in fact any algorithm
following the phase framework of Hopcroft and Karp, is adaptive to beneficial
input structure. We exhibit several graph classes for which such algorithms run
in linear time $\mathcal{O}(n+m)$. More strongly, we show that they run in time
$\mathcal{O}(\sqrt{k}m)$ for graphs that are $k$ vertex deletions away from any
of several such classes, without explicitly computing an optimal or approximate
deletion set; before, most such bounds were at least $\Omega(km)$. Thus, any
phase-based matching algorithm with linear-time phases obliviously interpolates
between linear time for $k=\mathcal{O}(1)$ and the worst case of
$\mathcal{O}(\sqrt{n}m)$ when $k=\Theta(n)$. We complement our findings by
proving that the phase framework by itself still allows $\Omega(\sqrt{n})$
phases, and hence time $\Omega(\sqrt{n}m)$, even on paths, cographs, and
bipartite chain graphs.
