# A reduction between small cliques problems

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

• Not exactly linear, but here's a simple solution that works better than quadratic, and takes only $O(|E|^{1.41})$ for directed graphs or $O(|E|^{1.34})$ for undirected: Use Alon's method for finding triangles, and output an empty graph, or a clique of size 9, depending on whether $G$ had a triangle.
– R B
Jan 14 '14 at 9:25
• @RB nice. I added a remark related to your comment. Jan 14 '14 at 10:13
• By $\text{maxclique}(G)$, do you mean the size of the largest clique in $G$? If so, I suggest you edit this to $\omega(G)$ (the clique number of $G$), which is more standard terminology.
– Juho
Jan 14 '14 at 13:48
• Don't you only need those vertices in G ⊠ G which are (v,v) and (v,w) where (v,w) ∈ E? I don't know think this will give you linear time, but it will be a lot less than quadratic. Jan 15 '14 at 22:30