Dynamic Matching Algorithms Under Vertex Updates

on YouTube ↗26m

" summary

Maintains maximal matchings under vertex insertions and deletions with a concrete tradeoff: a simple bipartite algorithm (one side fixed) is irrevocable and achieves constant amortized update time, but for irrevocable algorithms in the medium dynamic model there are polynomial lower bounds conditioned on OMV and triangle-detection conjectures. A different scheme allows at most one algorithmic deletion per update — a one-revocable algorithm — that runs in constant amortized time for general graphs. Also gives an e/(e-1)-approximate MCM under client arrivals/departures by dynamically maintaining the KVV ranking.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:58Dynamic matching algorithms
3. 1:46Standard dynamic setting
4. 4:50Recourse bound Recourse bound: #changes to the output matching per update
5. 5:43Previous work: vertex updates
6. 7:13Our contribution
7. 11:56Key takeaways . "i-revocable": more refined measure of recourse
8. 14:47Highly-revocable MM: preliminaries
9. 16:04Highly-revocable MM: handling safe vertices
10. 18:40Highly-revocable MM: handling risky vertices
11. 20:59Highly-revocable MM: running time
12. 21:311-revocable MM
13. 23:57Conclusion ► We initiate the study of fully dynamic graph matchings under vertex updates