# Problem 39: Approximating Maximum Matching Size

Suggested by | Krzysztof Onak |
---|---|

Source | Bertinoro 2011 |

Short link | https://sublinear.info/39 |

Consider graphs with maximum degree bounded by $d$. It is possible to approximate the size of the maximum matching up to an additive $\epsilon n$ in time that is a function of only $\epsilon$ and $d$ [NguyenO-08,YoshidaYI-09]. The fastest currently known algorithm runs in $d^{O(1/\epsilon^2)}$ time [YoshidaYI-09].

**Question:** Is there an algorithm that runs in $\operatorname{poly}(d/\epsilon)$ time?

## Update[edit]

Behnezhad, Roghani, and Rubinstein (FOCS 2023) showed that $d^{\Omega(1/\epsilon)}$ time is needed for this problem, therefore negatively resolving the open problem above.