TransWikia.com

approximate maximum clique given vertex cover

Theoretical Computer Science Asked by markHall on November 6, 2021

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?

One 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.

Answered by Nicolas GZ on November 6, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP