Linear programming based approximation for unweighted induced matchings -- breaking the barrier

DOI10.1016/J.DISOPT.2020.100593MaRDI QIDQ2218644zbMATH OpenOpenAlexFDO

Authors Julien Baste, Maximilian Fürst, Dieter Rautenbach

Publication date 15 January 2021

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.05930

zbMATH Keywords

approximation algorithminduced matchinglinear programmingprimal-dual approximation algorithmstrong matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05)

Abstract: A matching in a graph is induced if no two of its edges are joined by an edge, and finding a large induced matching is a very hard problem. Lin et al. (Approximating weighted induced matchings, Discrete Applied Mathematics 243 (2018) 304-310) provide an approximation algorithm with ratio $Delta$ for the weighted version of the induced matching problem on graphs of maximum degree $Delta$. Their approach is based on an integer linear programming formulation whose integrality gap is at least $Delta-1$, that is, their approach offers only little room for improvement in the weighted case. For the unweighted case though, we conjecture that the integrality gap is at most $frac58Delta+O(1)$, and that also the approximation ratio can be improved at least to this value. We provide primal-dual approximation algorithms with ratios $(1-epsilon)Delta+frac12$ for general $Delta$ with $epsilonapprox0.02005$, and $frac73$ for $Delta=3$. Furthermore, we prove a best-possible bound on the fractional induced matching number in terms of the order and the maximum degree.

Recommendations

• Approximating weighted induced matchings
• Induced matchings in graphs of bounded maximum degree
• Two greedy consequences for maximum induced matchings
• Approximation and Online Algorithms
• On the approximability of the maximum induced matching problem

Cites work

• Approximability results for the maximum and minimum maximal induced matching problems
• Approximating weighted induced matchings
• Approximation and Online Algorithms
• Graphs of prescribed girth and bi-degree
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Induced matchings in bipartite graphs
• Induced matchings in graphs of bounded maximum degree
• Induced matchings in subcubic graphs
• Locally searching for large induced matchings
• New results on maximum induced matchings in bipartite graphs and beyond
• On the approximability of the maximum induced matching problem
• Two greedy consequences for maximum induced matchings

Cited in

(4)

• Approximating weighted induced matchings
• Approximating maximum acyclic matchings by greedy and local search strategies
• Generalizing the induced matching by edge capacity constraints
• Structural parameterizations for induced and acyclic matching

This page was built for publication: Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2218644)