pipette
ESEspañol

A 2/3-Approximation Algorithm for the Residual Maximum Matching Problem in General Graphs

Quanlong Niu, Riheng Jia

Preprint

In the authors' words

The residual maximum matching problem asks for a maximum matching whose deletion leaves a graph with the largest possible matching number. For unweighted graphs, previous work provides a -approximation guarantee in general graphs and a guarantee in graphs with a perfect matching. We present a -approximation algorithm running in time, extending the latter guarantee to general graphs. The algorithm improves the residual matching number through single-edge exchanges involving free vertices. We prove that, for any maximum matching that admits no further improvement by such exchanges, the residual matching number is at least of the optimum, and we give an example showing that this bound is tight.

Main resultLimitation the authors admit

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.