<p>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.</p>

<ul>
<li>If $G$ contains a triangle, then $H$ contains a clique of size 9.</li>
<li>If $G$ contains no triangles, then $\mathrm{maxclique}(H) \leq 4$.</li>
<li>The reduction runs in time $O(|G|) = O(|V_G|+|E_G|)$.</li>
</ul>

<hr>

<p>A simple attempt would be to take $H=G\boxtimes K_3$, that is the <a href="http://en.wikipedia.org/wiki/Strong_product_of_graphs">strong direct product</a> of $G$ with $K_3$. This will give 9-vs-6, and not the required 9-vs-4.</p>

<p>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.</p>

<hr>

<p><strong>Remark 1:</strong> 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$.</p>

<hr>

<p><strong>Remark 2:</strong> 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).</p>

CC BY-SA 3.0
2014-01-14T09:25:42.493Z
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](http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf) method for finding triangles, and output an empty graph, or a clique of size 9, depending on whether $G$ had a triangle.
R B
CC BY-SA 3.0
2014-01-14T10:13:31.583Z
@RB nice. I added a remark related to your comment.
Igor Shinkar
CC BY-SA 3.0
2014-01-14T13:48:59.137Z
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
CC BY-SA 3.0
2014-01-15T22:30:25.130Z
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.
Peter Shor 
<reductions><clique>
A reduction between small cliques problems
Igor Shinkar
# A reduction between small cliques problems

(Asked by: username_0 on 2014-01-14)

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](http://en.wikipedia.org/wiki/Strong_product_of_graphs) 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).

**Tags:** reductions, clique

> **Comments:**
> **username_1**: 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](http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf) method for finding triangles, and output an empty graph, or a clique of size 9, depending on whether $G$ had a triangle.  
> **username_0**: @RB nice. I added a remark related to your comment.  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 0 answers

