Sensitivity Analysis of the Maximum Matching Problem
summary
Gives a randomized algorithm that achieves a 1+ε approximation with O(1) worst-case edge sensitivity (uses randomized greedy + McGregor’s layered augmenting-path sampler, O((n+m)·k) time with k = O(1/ε)), and a randomized greedy subroutine with expected O(1) modified edges. Presents a deterministic LCA-based maximal matching with worst-case sensitivity ≤ delta^{6^delta + log n} (uses a 6^delta coloring LCA plus Parnas–Ron simulation), proves any deterministic constant-factor matcher has sensitivity Ω(log n), and gives weighted-matching tradeoffs (four-α approx: weighted sensitivity W log n for α=2, W for α>2).
AI-written summary · about