Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems

We study theMinimum Maximal Matching problem, where we are asked to find in a graph the smallest matching that cannot be extended. We show that this problem is hard to approximate with any constant smaller than 2 even in bipartite graphs, assuming either of two stronger variants of Unique Games Conjecture. The bound also holds for computationally equivalent Minimum Edge Dominating Set. Our lower bound matches the approximation provided by a trivial algorithm. Our results imply conditional hardness of approximating Maximum Stable Matching with Ties and Incomplete Lists with a constant better than 3/2, which also matches the best known approximation algorithm

• Algorithms and Theory