2026-08-17T08:57:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18117 2024-03-06T11:01:04Z ddc:004 open_access

Matching Augmentation via Simultaneous Contractions Garg, Mohit Hommelsheim, Felix Megow, Nicole matching augmentation approximation algorithms 2-edge-connectivity We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a 2-edge-connected spanning subgraph by adding the minimum number of edges to it. We present a polynomial-time algorithm with an approximation ratio of 13/8 = 1.625 improving upon an earlier 5/3-approximation. The improvement builds on a new α-approximation preserving reduction for any α ≥ 3/2 from arbitrary MAP instances to well-structured instances that do not contain certain forbidden structures like parallel edges, small separators, and contractible subgraphs. We further introduce, as key ingredients, the technique of repeated simultaneous contractions and provide improved lower bounds for instances that cannot be contracted. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohit Garg and Felix Hommelsheim and Nicole Megow 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.65 urn:nbn:de:0030-drops-181176 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.65 eng https://creativecommons.org/licenses/by/4.0/legalcode