Locally searching for large induced matchings

DOI10.1016/J.TCS.2018.02.006MaRDI QIDQ1704586zbMATH OpenOpenAlexFDO

Authors Maximilian Fürst, Marilena Leichter, Dieter Rautenbach

Publication date 12 March 2018

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• Approximation and Online Algorithms
• 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
• Induced matchings in intersection graphs.
• NP-completeness of some generalizations of the maximum matching problem
• New results on maximum induced matchings in bipartite graphs and beyond
• On distance-3 matchings and induced matchings
• On maximum induced matchings in bipartite graphs
• On the approximability of the maximum induced matching problem
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Two greedy consequences for maximum induced matchings

Cited in

(7)

• Matroid matching: the power of local search
• Approximating weighted induced matchings
• Approximating maximum acyclic matchings by greedy and local search strategies
• Linear programming based approximation for unweighted induced matchings -- breaking the \(\varDelta\) barrier
• Approximation and Online Algorithms
• 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)