<p>Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good.</p>
<p>Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find it within polynomial time. Or it is not and thus 1+1/OPT is better than 1+epsilon.</p>

CC BY-SA 4.0
2020-07-21T16:42:33.653Z
2020-07-21T17:07:09.767Z
2020-07-21T17:07:09.767Z
Nicolas GZ
<p>I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique of G. One thing I got is that every clique in G can contain at most 1 vertex not in the vertex cover, so a linear kernel can be constructed by removing all vertices not in the vertex cover and then I lose at most 1 vertex from the optimal max clique. The problem is that for small enough epsilon being 1 off is not good enough. Am I missing something or is this the best linear kernel possible?</p>

<graph-algorithms><approximation-algorithms><reductions><clique><vertex-cover>
approximate maximum clique given vertex cover
markHall
# approximate maximum clique given vertex cover

(Asked by: username_0 on 2020-07-21)

I have a non optimal vertex cover of size k of a graph G, and I want to get a (1+epsilon)-approximation kernel of size linear in k for maximum clique of G. One thing I got is that every clique in G can contain at most 1 vertex not in the vertex cover, so a linear kernel can be constructed by removing all vertices not in the vertex cover and then I lose at most 1 vertex from the optimal max clique. The problem is that for small enough epsilon being 1 off is not good enough. Am I missing something or is this the best linear kernel possible?

**Tags:** graph-algorithms, approximation-algorithms, reductions, clique, vertex-cover


---

## 1 answers

### Answer by username_1 on 2020-07-21. Score: 1 | Accepted answer

Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good.

Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find it within polynomial time. Or it is not and thus 1+1/OPT is better than 1+epsilon.


---

