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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
