<p>One important reason why problems that look equally hard to compute exactly might be very different to approximate relates to the fragility of NP-completeness reductions. </p>

<p>The simplest example I can think of the relation between VERTEX COVER and MAX INDEPENDENT SET. The two problems are complementary: given a graph $G = (V, E)$ with a vertex cover $S$, the set $V\setminus S$ is an independent set. This is why it's easy to show that one problem is NP-hard by reduction from the other. </p>

<p>But suppose I can get "close" to a good vertex cover, in that instead of finding the smallest cover $S$, I find a worse cover $S'$ where $|S'| = 2 |S|$. This means that instead of finding the maximum independent set of size $n - |S|$, I've found one of size $n - 2|S|$. </p>

<p>Suppose in this graph the max independent set size was $n/2$. Then essentially my approximation to the vertex cover found nothing at all. </p>

<p>In other words, the NP-hardness reduction only preserved the <em>exact</em> solution relationship, not the <em>approximate</em> solution relationship. </p>

<p>To preserve approximations, you need a different kind of reduction called an $L$-reduction, and once you limit yourself to such reductions, you realize that the two problems are indeed quite different. </p>

CC BY-SA 3.0
2015-04-12T10:52:54.893Z
Thanks! Does harder to approximate implies the problem more local minima?
Yushi Xiao
CC BY-SA 3.0
2015-04-12T07:10:18.887Z
2015-04-12T07:10:18.887Z
Suresh Venkat
<p>I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem.</p>

<p>To my surprise, some closely related NP-hard problems are quite different in terms of approximation.</p>

<p>Can anyone give me some intuition behind this phenomenon?</p>

<p>Thanks in advance!</p>

CC BY-SA 3.0
2015-04-11T20:23:01.960Z
Cross-posted to http://mathoverflow.net/questions/202651
Emil Jeřábek
CC BY-SA 3.0
2015-04-11T21:07:13.460Z
Can you provide a link to the paper?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-04-13T03:53:11.893Z
The question has been asked before on cs.se, and received a very similar answer.
Yuval Filmus
<cc.complexity-theory><graph-algorithms><approximation-algorithms>
What is the intuition behind "hardness of approximation"?
Yushi Xiao
# What is the intuition behind "hardness of approximation"?

(Asked by: username_0 on 2015-04-11)

I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem.

To my surprise, some closely related NP-hard problems are quite different in terms of approximation.

Can anyone give me some intuition behind this phenomenon?

Thanks in advance!

**Tags:** cc.complexity-theory, graph-algorithms, approximation-algorithms

> **Comments:**
> **username_1**: Cross-posted to http://mathoverflow.net/questions/202651  
> **username_2**: Can you provide a link to the paper?  
> **username_3**: The question has been asked before on cs.se, and received a very similar answer.  

---

## 1 answers

### Answer by username_4 on 2015-04-12. Score: 6 | Accepted answer

One important reason why problems that look equally hard to compute exactly might be very different to approximate relates to the fragility of NP-completeness reductions.

The simplest example I can think of the relation between VERTEX COVER and MAX INDEPENDENT SET. The two problems are complementary: given a graph $G = (V, E)$ with a vertex cover $S$, the set $V\setminus S$ is an independent set. This is why it's easy to show that one problem is NP-hard by reduction from the other.

But suppose I can get "close" to a good vertex cover, in that instead of finding the smallest cover $S$, I find a worse cover $S'$ where $|S'| = 2 |S|$. This means that instead of finding the maximum independent set of size $n - |S|$, I've found one of size $n - 2|S|$.

Suppose in this graph the max independent set size was $n/2$. Then essentially my approximation to the vertex cover found nothing at all.

In other words, the NP-hardness reduction only preserved the *exact* solution relationship, not the *approximate* solution relationship.

To preserve approximations, you need a different kind of reduction called an $L$-reduction, and once you limit yourself to such reductions, you realize that the two problems are indeed quite different.

> **Comments:**
> **username_0**: Thanks! Does harder to approximate implies the problem more local minima?  

---

