Output Sensitive Fault Tolerant Maximum Matching

We consider the problem of maintaining the size of a Maximum Matching in the presence of failures of vertices and edges. For a graph G, we use μ(G) to denote the size of a maximum matching of G. A subgraph H of G is an (α, f) -Fault Tolerant Matching Subgraph ((α, f) -FTMS) if it has the following property: For any set F of at most f vertices or edges in G, α· μ(G- F) ≤ μ(H- F). Assadi and Bernstein [SOSA 2019] showed that for any ϵ> 0, there exists a (23-ϵ,f) -FTMS of size O(n+ f). In this paper we initiate a study of (1, f)-FTMS or f-FTMS in short. In particular we obtain the following results, On bipartite graphs, there exists 1-FTMS, for one edge fault with O(μ(G) ) vertices and edges. We complement this upper bound with the matching lower bound of Ω(μ(G) ) on 1-FTMS for one edge fault.On general graphs, there exists f-FTMS for at most f edge faults with O(μ(G) ²+ μ(G) f) edges and O(μ(G) · f) vertices. We also provide a matching lower bound of Ω(max { μ(G) ², μ(G) f} ) edges and Ω(μ(G) f) vertices for f-FTMS, f≥ 2 for at most f edge faults. The same construction works for vertex faults, and they result in even tighter bounds for f= 1. Our algorithmic results exploit the structural properties of matchings and use tools from Parameterized Algorithms, such as Expansion Lemma. We leave open the question of existence of 1-FTMS for one edge fault, of linear size (in terms of μ(G) ) on general graphs.