I have two similar problems in which I'm trying to find a connection to help me solve one of them.

In the first one I'm given a graph G = (V,E) , integer k, and vertex cover U of size k. The objective is to find the largest clique (max size clique in G).

The second one is instead of a vertex cover, U is is a group of vertices that make so that G - U is planar graph.

What I'm searching for is to show that given any $ \epsilon > 0 $ the problem admits $ 1+ \epsilon $ approximate kernel of size linear in k.

When the input is as in the first problem and I get a vertex cover I successfully manage to show that, So my actual question is is there any relation between U being vertex cover and that removing U making the graph planar?

I know that the max size clique of the graph G[G-U] is at most 4, but I don't know if U has any cliques or maybe even U has vertices that with G-U create a bigger clique.

  • $\begingroup$ What happens when your graph contains two disjoint cliques? $\endgroup$
    – nir shahar
    Jul 13 at 8:11
  • $\begingroup$ If both of them are of max size, it doesn't matter which of them you find $\endgroup$
    – jsitesting
    Jul 13 at 8:17
  • $\begingroup$ My point is. What happens when you remove one? The other one stays. Hence the graph is not planar (if the cliques are of size at least 5) $\endgroup$
    – nir shahar
    Jul 13 at 9:19
  • $\begingroup$ That's true (even if you have one clique of size at least 5 it's not planar), I'm just trying to find if I can make any conclusion that relate the two problems $\endgroup$
    – jsitesting
    Jul 13 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.