In multistage perfect matching problems we are given a sequence of graphs on the same vertex set and are asked to find a sequence of perfect matchings, corresponding to the sequence of graphs, such that consecutive matchings are as similar as possible. More precisely, we aim to maximize the intersections, or minimize the unions between consecutive matchings. We show that these problems are NP-hard even in very restricted scenarios. As our main contribution, we present the first non-trivial approximation algorithms for these problems: On the one hand, we devise a tight 2-stage approximation. On the other hand, we propose multiple general methods to deduce multistage approximations from blackbox 2-stage approximations.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_39