<p>Check out</p>

<blockquote>
  <p>Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai:<br>
  "Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses"<br>
  Link:  <a href="https://arxiv.org/abs/1308.2617" rel="nofollow noreferrer">https://arxiv.org/abs/1308.2617</a></p>
</blockquote>

CC BY-SA 3.0
2017-06-20T14:45:32.073Z
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?
Don Fanucci
CC BY-SA 3.0
2017-06-19T10:09:26.767Z
2017-06-19T10:09:26.767Z
Gamow
<p>We say that $H$ is a <strong>matching graph</strong> if it contains $2n$ vertices and only $n$ vertex-disjoint edges, i.e. $H$ only contains those $n$ edges and no more.</p>

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

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

<p>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)$:</p>

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

<p>$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. </p>

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

<p>I wanted to say that:</p>

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

<p>I failed doing so. Can someone help?</p>

CC BY-SA 3.0
2017-06-20T20:29:01.093Z
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
<cc.complexity-theory><approximation-algorithms><reductions><approximation-hardness>
hardness of constant approximation of largest matching set
Don Fanucci
# hardness of constant approximation of largest matching set

(Asked by: username_0 on 2017-06-19)

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?

**Tags:** cc.complexity-theory, approximation-algorithms, reductions, approximation-hardness

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2017-06-19. Score: 1

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>

> **Comments:**
> **username_0**: 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?  

---

