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

  • 1
    $\begingroup$ 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. $\endgroup$
    – R B
    Jan 14 '14 at 9:25
  • $\begingroup$ @RB nice. I added a remark related to your comment. $\endgroup$ Jan 14 '14 at 10:13
  • $\begingroup$ 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. $\endgroup$
    – Juho
    Jan 14 '14 at 13:48
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 15 '14 at 22:30

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.