-1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.