Three results towards the approximation of special maximum matchings in graphs

For a graph $G$ define the parameters $\mathrm{\ell }(G)$ and $L(G)$ as the minimum and maximum value of $\nu (G\mathrm{\backslash }F)$, where $F$ is a maximum matching of $G$ and $\nu (G)$ is the matching number of $G$. In this paper, we show that there is a small constant $c>0$, such that the following decision problem is NP-complete: given a graph $G$ and $k\le \frac{\mathrm{\mid }V\mathrm{\mid }}{2}$, check whether there is a maximum matching $F$ in $G$, such that $\mathrm{\mid }\nu (G\mathrm{\backslash }F)-k\mathrm{\mid }\le c\cdot \mathrm{\mid }V\mathrm{\mid }$. Note that when $c=1$, this problem is polynomial time solvable as we observe in the paper. Since in any graph $G$, we have $L(G)\le 2\mathrm{\ell }(G)$, any polynomial time algorithm constructing a maximum matching of a graph is a 2-approximation algorithm for $\mathrm{\ell }(G)$ and $\frac{1}{2}$-approximation algorithm for $L(G)$. We complement these observations by presenting two inapproximability results for $\mathrm{\ell }(G)$ and $L(G)$.