1
$\begingroup$

Say you write a round-k Lasserre (or any other hierarchy!) SDP relaxation of the Max-Clique problem. Lets say one now finds (or knows how to sample with high probability) a graph $G_1$ of size $n$ and produce for this graph a certificate for the SDP which corresponds to having found a clique of size $n^\alpha$ in $G_1$ for some $\alpha \in (0,1]$.

Now using this certificate (or any other means!) is it possible to construct another graph $G_2$ of size $N$ (might be necessary that $N>n$) and a certificate for it for this same SDP which would correspond to having found a $N^{ 1-\epsilon }$ size clique in $G_2$ for some $1 - \epsilon > \alpha$? (its okay even if $G_2$ is shown to exist in some probabilistic sense)

Are there examples of doing such a blow-up of the objective value for a Max-Clique SDP?


Not sure if its immediately related but putting this out here : Is there any obvious reason why this very famous paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf does not deal with Max-Clique? Isn't it true that the complement of the Max-Independent-Set integrality gap instance does not give the integrality gap instance of Max-Clique?

$\endgroup$
  • $\begingroup$ Please ask only one question per post. You can ask the second question separately, with a link to this question. $\endgroup$ – Jan Johannsen Jun 1 '16 at 8:58
  • $\begingroup$ Yes, but I thought this reference helps put the question in context.. $\endgroup$ – Anirbit Jun 1 '16 at 13:18

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.