论文标题
通过同时收缩匹配增强
Matching Augmentation via Simultaneous Contractions
论文作者
论文摘要
我们考虑匹配的增强问题（MAP），其中图形的匹配需要通过向其添加最小边数来扩展到$ 2 $ - 边缘连接的跨度子图。我们提出了一种多项式时间算法，其近似值为$ 13/8 = 1.625 $，以较早的$ 5/3 $ - APPRXIMATION改善。这些改进是基于新的$α$ Approximation保留任何$α\ geq 3/2 $从任意地图实例到结构良好的实例，这些实例不包含某些禁止结构，例如平行边缘，小型分离器和可签名的子分类。我们进一步介绍了重复同时收缩的技术，并为无法收缩的情况提供了改进的下限。
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 $α\geq 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.
