Tight approximation ratio for Minimum Maximal Matching

DOI10.1007/978-3-030-17953-3_14MaRDI QIDQ2293087zbMATH OpenOpenAlexFDO

Authors Szymon Dudycz, Mateusz Lewandowski, Jan Marcinkowski

Publication date 6 February 2020

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We study a combinatorial problem called Minimum Maximal Matching, where we are asked to find in a general graph the smallest that can not be extended. We show that this problem is hard to approximate with a constant smaller than 2, assuming the Unique Games Conjecture. As a corollary we show, that Minimum Maximal Matching in bipartite graphs is hard to approximate with constant smaller than $frac43$, with the same assumption. With a stronger variant of the Unique Games Conjecture --- that is Small Set Expansion Hypothesis --- we are able to improve the hardness result up to the factor of $frac32$.

Recommendations

• Hardness and approximation of minimum maximal matchings
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• Algorithms and Computation
• scientific article; zbMATH DE number 5799830
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs

Cited in

(14)

• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• scientific article; zbMATH DE number 2081000 (Why is no real title available?)
• Multitasking capacity: hardness results and improved constructions
• Computing and Combinatorics
• Extension of some edge graph problems: standard, parameterized and approximation complexity
• scientific article; zbMATH DE number 7764100 (Why is no real title available?)
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Max-min greedy matching problem: hardness for the adversary and fractional variant
• Minimal zero forcing sets
• Minimum maximal matchings in permutahedra

This page was built for publication: Tight approximation ratio for Minimum Maximal Matching

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