  Suppose we are given a bipartite graph that admits a perfect matching and an
adversary may delete any edge from the graph with the intention of destroying
all perfect matchings. We consider the task of adding a minimum cost edge-set
to the graph, such that the adversary never wins. We provide efficient exact
and approximation algorithms. In particular, for the unit-cost problem, we
provide a $\log_2 n$-factor approximation algorithm and a polynomial-time
algorithm for chordal-bipartite graphs. Furthermore, we give a fixed parameter
algorithm for the problem parameterized by the treewidth of the input graph.
For general non-negative weights we settle the approximability of the problem
and show a close relation to the Directed Steiner Forest Problem. Additionally
we prove a dichotomy theorem characterizing minor-closed graph classes which
allow for a polynomial-time algorithm. Our methods rely on a close relationship
to the classical strong connectivity augmentation problem and directed Steiner
problems.
