Approximating weighted induced matchings

作者：Min Chih Lin; Mestre Julian; Vasiliev Saveliy^*

来源：Discrete Applied Mathematics, 2018, 243: 304-310.

DOI：10.1016/j.dam.2018.01.009

• Approximation algorithms
• Maximum induced matching

An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Delta, for Delta >= 3, is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Delta, which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K-1,K-k-free graphs yields an approximation ratio 2k - 3. We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to (K-1,K-k, chair)-free graphs.

• 出版日期2018-7-10