I'm looking for a reduction that gets a graph $G=(V_G,E_G)$ and outputs a graph $H$ that satisfies the following requirements.If $G$ contains a triangle, then $H$ contains a clique of size 9.If $G$ contains no triangles, then $\mathrm{maxclique}(H) \leq 4$.The reduction runs in time $O(|G|) = O(|V_G|+|E_G|)$.A simple attempt would be to take $H=G\boxtimes K_3$, that is the strong direct product of $G$ with $K_3$. This will give 9-vs-6, and not the required 9-vs-4.Another attempt would be to try taking $H=G\boxtimes G$ to be the strong direct product of $G$ with itself. This satisfies the first two requirements, but the running time is quadratic. On the other hand, this construction gives something stronger, namely, if $\mathrm{maxclique}(G)=k$, then $\mathrm{maxclique}(H) = k^2$ regardless of the value of $k$. So maybe there is hope to change this product so that it works only for $k=2,3$ in linear time.Remark 1: Note that we don't expect to have a linear time algorithm for finding a triangle, so I want a real reduction, and not an algorithm that looks for triangles in $G$.Remark 2: Alternatively, I'd be happy with an explanation why such reduction is unlikely to exist (e.g., because the 9-vs-4 problem can be solved in linear time).
A reduction between small cliques problems
reductions;clique