# hardness of constant approximation of largest matching set

We say that $H$ is a matching graph if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.

Given a graph $G=(V,E)$ a subset $U\subseteq V$ is called a matching set if the sub graph that is induced by $U$ is a matching graph.

Prove that approximating the problem of finding the largest matching set is $NP-Hard$ for any constant factor.

I tried reducing to it from the $IS$ problem. I know that it is $NP-Hard$ to approximate $IS$ for any constant factor. I thought of this reduction, given a graph $G=(V,E)$:

$1)$ Find $k=\max\limits_{\ v\in V} deg(v)$.

$2)$ Construct $k$ graphs exactly like $G$: $G_1(V_1,E_1),\dots,G_k(V_k,E_k)$. those graphs are exactly like $G$ but the vertices are signed by the index and so does the edges.

$3)$ Return $H=(\cup_{i} V_i,\cup E_i)$.

I wanted to say that:

If $m$ is the size of the maximal $IS$ in $G$, the size of the largest matching set in $H$ is: $k\ \cdot m$.

I failed doing so. Can someone help?

• Here's a way to do it. On input graph $(V, E)$, output a graph with vertices $V \times \{0,1\}$ and edges $\{((v, i), (u, j))~|~u=v\text{ or }(u,v)\in E\}$. An independent set $I$ in $(V, E)$ of size $k$ can be converted into a matching set $I \times \{0,1\}$ of size $2k$ in the output graph. Similarly, a matching set of size $2k$ can be converted into an independent set in the input graph of size $k$ by choosing one vertex $(v, i)$ from each edge of the matching set and taking only the $v$ part. None of these vertices are adjacent since they are from different edges in the (induced) matching. – Mikhail Rudoy Jun 20 '17 at 20:29