Google Research

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

Workshop on Approximation and Online Algorithms (WAOA) (2021) (to appear)


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

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work