2026-07-25T00:57:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10277 2024-03-06T10:45:42Z ddc:004 open_access

How to Secure Matchings Against Edge Failures Hommelsheim, Felix Mühlenthaler, Moritz Schaudt, Oliver Matchings Robustness Connectivity Augmentation Graph Algorithms Treewidth 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 show that this problem is equivalent to covering a digraph with non-trivial strongly connected components at minimal cost. We provide efficient exact and approximation algorithms for this task. In particular, for the unit-cost problem, we give 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 give tight upper and lower approximation bounds relative to the Directed Steiner Forest problem. Additionally we prove a dichotomy theorem characterizing minor-closed graph classes which allow for a polynomial-time algorithm. To obtain our results, we exploit a close relation to the classical Strong Connectivity Augmentation problem as well as directed Steiner problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Felix Hommelsheim and Moritz Mühlenthaler and Oliver Schaudt 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.38 urn:nbn:de:0030-drops-102772 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.38 eng https://creativecommons.org/licenses/by/3.0/legalcode