Decomposition Algorithms for Solving the Minimum Weight Maximal Matching Problem

摘要

We investigate the problem of finding a maximal matching that has minimum total weight on a given edge-weighted graph. Although the minimum weight maximal matching problem is NP-hard in general, polynomial time exact or approximation algorithms on several restricted graph classes are given in the literature. In this article, we propose an exact algorithm for solving several variants of the problem on general graphs. In particular, we develop integer programming (IP) formulations for the problem and devise a decomposition algorithm, which is based on a combination of IP techniques and combinatorial matching algorithms. Our computational tests on a large suite of randomly generated graphs show that our decomposition approach significantly improves the solvability of the problem compared to the underlying IP formulation.