{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T02:28:26Z","timestamp":1790562506421,"version":"4.1.0"},"reference-count":30,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>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 nontrivial 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 nonnegative 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.<\/jats:p>","DOI":"10.1137\/20m1336229","type":"journal-article","created":{"date-parts":[[2021,9,28]],"date-time":"2021-09-28T12:12:50Z","timestamp":1632831170000},"page":"2265-2292","source":"Crossref","is-referenced-by-count":4,"title":["How to Secure Matchings against Edge Failures"],"prefix":"10.1137","volume":"35","author":[{"given":"Felix","family":"Hommelsheim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moritz","family":"Muehlenthaler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oliver","family":"Schaudt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,9,28]]},"reference":[{"key":"atypb1","first-page":"1","author":"Adjiashvili D.","year":"2016","journal-title":"Germany"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0760-6"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2010.12.018"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.007"},{"key":"atypb5","unstructured":"V. Bindewald,\n                      Bulk-Robust Assignment Problems: Hardness, Approximability and Algorithms\n                      , Ph.D. thesis, Fakult\u00e4t f\u00fcr Mathematik, TU Dortmund University, 2018,https:\/\/doi.org\/10.17877\/DE290R-19108."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106717"},{"key":"atypb9","first-page":"185","volume":"174","author":"Brigham R. C.","year":"2005","journal-title":"Congr. Numer."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/1921659.1921664"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1002\/net.20187"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01394-z"},{"key":"atypb13","first-page":"170","volume":"14","author":"Cheriyan J.","year":"2001","journal-title":"Discrete Math."},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized Algorithms\n                      , Springer, Cham, 2015,https:\/\/doi.org\/10.1007\/978-3-319-21275-3.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb15","first-page":"624","author":"Dinur I.","year":"2014","journal-title":"ACM"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1002\/net.21624"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1958-052-0"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441241"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.05.009"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0210019"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/net.20289"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"E. Halperin and R. Krauthgamer,\n                      Polylogarithmic inapproximability\n                      , in Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing - STOC '03, ACM Press, 2003, pp. 585-594,https:\/\/doi.org\/10.1145\/780542.780628.","DOI":"10.1145\/780542.780628"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/0606070"},{"key":"atypb25","first-page":"1","author":"Hommelsheim F.","year":"2019","journal-title":"STACS"},{"key":"atypb26","unstructured":"T. Jel\u00ednek,\n                      Implementing Robust Matching Augmentation\n                      , bachelor's thesis, Faculty of Informatikcs, Masaryk University, 2019."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.065"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"H. Nagamochi and T. Ibaraki,\n                      Connectivity Augmentation\n                      , in Graph Connectivity Augmentation, Cambridge University Press, 2015, pp. 246-281,https:\/\/doi.org\/10.1017\/cbo9780511721649.009.","DOI":"10.1017\/CBO9780511721649.009"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"G. Nemhauser and L. Wolsey,\n                      Integer and Combinatorial Optimization\n                      , Wiley Ser. Discrete Math. Optim., John Wiley & Sons, New York,https:\/\/doi.org\/10.1002\/9781118627372.","DOI":"10.1002\/9781118627372"},{"key":"atypb30","unstructured":"V. Traub and R. Zenklusen,\n                      A Better-than-2 Approximation for Weighted Tree Augmentation\n                      , arXiv preprint, arXiv:2104.07114 [CS.DS], 2021."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1336229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:36Z","timestamp":1787321256000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1336229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1336229"],"URL":"https:\/\/doi.org\/10.1137\/20m1336229","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}