A Generalized Matching Reconfiguration Problem
summary
Shows a linear-time procedure that reconfigures any unweighted source matching into any target matching while keeping intermediate matchings within one of the larger size and allowing adjacent steps of delta = 3 changes; sometimes two-unit drops are necessary but never more. For weighted matchings the process limits weight loss to about the maximum edge weight W (and can trade larger delta ≈ 1/ε for a (1−ε) multiplicative guarantee). Gives a black-box reduction turning any dynamic MCM algorithm with update time T into one with similar T and worst-case recourse O(1/ε) (weighted costs scale by W), and proves 1/ε recourse is optimal for (1+ε)-approximation.
AI-written summary · about