摘要：The goal in reconfiguration problems is to compute a gradual transformation between two feasible solutions of a problem such that all intermediate solutions are also feasible. In the Matching Reconfiguration Problem (MRP), proposed in a pioneering work by Ito et al. from 2008, we are given a graph G and two matchings M and M', and we are asked whether there is a sequence of matchings in G starting with M and ending at M', each resulting from the previous one by either adding or deleting a single edge in G, without ever going through a matching of size 0, can be transformed into an algorithm for maintaining a (β(1 ε))-approximate maximum cardinality matching with update time T O(1/ε) and worst-case recourse bound O(1/ε). This result generalizes for approximate maximum weight matching, where the update time and worst-case recourse bound grow from T O(1/ε) and O(1/ε) to T O(Ï^/ε) and O(Ï^/ε), respectively; Ï^ is the graph aspect-ratio. We complement this positive result by showing that, for β = 1 ε, the worst-case recourse bound of any algorithm produced by our reduction is optimal. As a corollary, several key dynamic approximate matching algorithms - with poor worst-case recourse bounds - are strengthened to achieve near-optimal worst-case recourse bounds with no loss in update time.
