Locally searching for large induced matchings

DOI10.1016/J.TCS.2018.02.006zbMATH Open1388.68230arXiv1708.02028OpenAlexW2742438336MaRDI QIDQ1704586FDOQ1704586

Authors: Maximilian Fürst, Marilena Leichter, Dieter Rautenbach 

Publication date: 12 March 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: It is an easy observation that a natural greedy approach yields a $left(d-O(1)ight)$-factor approximation algorithm for the maximum induced matching problem in $d$-regular graphs. The only considerable and non-trivial improvement of this approximation ratio was obtained by Gotthilf and Lewenstein using a combination of the greedy approach and local search, where understanding the performance of the local search was the challenging part of the analysis. We study the performance of their local search when applied to general graphs, $C_4$-free graphs, $C_3,C_4$-free graphs, $C_5$-free graphs, and claw-free graphs. As immediate consequences, we obtain approximation algorithms for the maximum induced matching problem restricted to the $d$-regular graphs in these classes.

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

Recommendations

• Two greedy consequences for maximum induced matchings
• Approximation and Online Algorithms
• On the approximability of the maximum induced matching problem
• Publication:4944970
• Approximating weighted induced matchings

zbMATH Keywords

local searchinduced matchingstrong matching

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• On maximum induced matchings in bipartite graphs
• NP-completeness of some generalizations of the maximum matching problem
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• New results on maximum induced matchings in bipartite graphs and beyond
• Title not available (Why is that?)
• On the approximability of the maximum induced matching problem
• Induced matchings in intersection graphs.
• On distance-3 matchings and induced matchings
• Two greedy consequences for maximum induced matchings
• Approximation and Online Algorithms

Cited In (7)

• Matroid matching: the power of local search
• Approximating weighted induced matchings
• Approximating maximum acyclic matchings by greedy and local search strategies
• Approximation and Online Algorithms
• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
• A Local Computation Approximation Scheme to Maximum Matching
• Two greedy consequences for maximum induced matchings

This page was built for publication: Locally searching for large induced matchings

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