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.