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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Mikhail Rudoy Jun 20 '17 at 20:29

Check out

Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai:
"Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses"
Link: https://arxiv.org/abs/1308.2617

  • $\begingroup$ I am sorry but this is a graduate level paper. I don't see the reduction from IS to Max-Matching. Their reduction is from IS to a more specific problem. Can you help or am I missing something. Do you have a reference to the more general version of mine? $\endgroup$ – Don Fanucci Jun 20 '17 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.