| Article ID: | iaor201528823 |
| Volume: | 66 |
| Issue: | 3 |
| Start Page Number: | 210 |
| End Page Number: | 213 |
| Publication Date: | Oct 2015 |
| Journal: | Networks |
| Authors: | Rautenbach Dieter, Dourado Mitre Costa, Meierling Dirk, Penso Lucia D, Protti Fabio, de Almeida Aline Ribeiro |
| Keywords: | matching |
We study perfect matchings M in graphs G that have the two properties of being robust as well as recoverable; where robust means that the failure of a set F ′ of not too many edges of G can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, G − F ′ has a perfect matching M ′ for which the symmetric difference of M and M ′ is small. We establish the hardness of several related algorithmic problems and identify some tractable cases. Among others we show the hardness of the well known matching preclusion number of a graph.